元素和小于等于阈值的正方形的最大边长

LeetCode 1292

元素和小于等于阈值的正方形的最大边长

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。

示例1：

输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
输出：2
解释：总和小于 4 的正方形的最大边长为 2，如图所示。

解法1：动态规划

解题思路：

可以用动态规划的思想计算出每一个正方形的元素和，然后遍历这些元素和得到结果

dp数组的含义是从(0,0)到(i,j)的元素和

因此动态规划转移方程为

dp[i][j] =  dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]

每一个边长为k的正方形的元素和为

sum = dp[i][j] - dp[i-k][j] - dp[i][j-k] + dp[i-k][j-k]

代码如下：

class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length, n = mat[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }
        int ans = 0;
        for (int k = 1; k <= Math.min(m, n); k++) {
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i - k < 0 || j - k < 0) {
                        continue;
                    }
                    int tmp = dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k];
                    if (tmp <= threshold) {
                        ans = Math.max(ans, k);
                    }
                }
            }
        }
        return ans;
    }
}

时间复杂度为O(min(M,N)*M*N)

解法2：动态规划+二分法

解题思路：

我们在前面动态规划的基础下，选择边长k时采用二分的方法，也就是在满足元素和小于阈值的情况下，尽可能的采用较大的边长

代码如下：

class Solution {
    int m, n;
    int[][] dp;
    public int maxSideLength(int[][] mat, int threshold) {
        m = mat.length;
        n = mat[0].length;
        dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) 
        {
            for (int j = 1; j <= n; j++) 
            {
                dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }
        int l = 0, h = Math.min(m, n);
        while (l <= h) 
        {
            int mid = l + (h - l) / 2;
            if (l == h || l + 1 == h) 
            {
                break;
            }
            if (help(mid, threshold)) 
            {
                l = mid;
            } 
            else 
            {
                h = mid - 1;
            }
        }
        if (help(h, threshold)) 
        {
            return h;
        } 
        else 
        {
            return l;
        }
    }
    public boolean help(int k, int threshold) {
        for (int i = 1; i <= m; i++) 
        {
            for (int j = 1; j <= n; j++) 
            {
                if (i - k < 0 || j - k < 0) 
                {
                    continue;
                }
                if (dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k] <= threshold) 
                {
                    return true;
                }
            }
        }
        return false;
    }
}

时间复杂度为O(log2(min(M,N)*M*N)

解法来源

作者：hlxing
链接：https://leetcode-cn.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/solution/qing-xi-tu-jie-mo-neng-de-qian-zhui-he-by-hlxing/
来源：力扣（LeetCode）
side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/solution/qing-xi-tu-jie-mo-neng-de-qian-zhui-he-by-hlxing/