【LeetCode 1292】 Maximum Side Length of a Square with Sum Less than or Equal to Threshold

题目描述

Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0

Example 3:

Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3

Example 4:

Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2

Constraints:

1 <= m, n <= 300
m == mat.length
n == mat[i].length
0 <= mat[i][j] <= 10000
0 <= threshold <= 10^5

思路

先用动态规划求出从（0,0）点到任意位置组成的矩形的面积。那么就可以在 O(1)的时间求出任意矩形的面积。最后遍历起始位置和边长，求出符合条件的最大边长。因为随着边长扩张，sum一定是增大的，可以用二分来求。时间复杂度 O ( mnlog(min(m, n)))。

代码

class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
             
        for (int i=1; i<=m; ++i){
            for (int j=1; j<=n; ++j) {
                dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mat[i-1][j-1];
            }
        }
        
        auto getSum = [&](int x1, int y1, int x2, int y2) {
            return dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
        };
        
        int ans = 0;
        for (int i=1; i<=m; ++i) {
            for (int j=1; j<=n; ++j) {
                int l = 0;
                int r = min(m-i, n-j) + 1;
                while(l < r) {
                    int mid = l + (r - l) / 2;
                    if (getSum(i, j, i+mid, j+mid) > threshold) {
                        r = mid;
                    }else l = mid + 1;
                }
                ans = max(ans, l);
            }
        }
        
        return ans;
    }
};

突然发现，每次对二分的边界条件都是试出来的。。。。
闭区间的二分：

class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
             
        for (int i=1; i<=m; ++i){
            for (int j=1; j<=n; ++j) {
                dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mat[i-1][j-1];
            }
        }
        
        auto getSum = [&](int x1, int y1, int x2, int y2) {
            return dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
        };
        
        int ans = 0;
        for (int i=1; i<=m; ++i) {
            for (int j=1; j<=n; ++j) {
                int l = 0;
                int r = min(m-i, n-j);
                while(l <= r) {
                    int mid = l + (r - l) / 2;
                    if (getSum(i, j, i+mid, j+mid) > threshold) {
                        r = mid - 1;
                    }else l = mid + 1;
                }
                ans = max(ans, l-1+1);
            }
        }
        
        return ans;
    }
};