欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-06 21:56:20
...

题目描述

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;
    }
};