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
Solution: DP + Brute Force
Precompute the sums of sub-matrixes whose left-top corner is at (0,0).
Try all possible left-top corner and sizes.
Time complexity: O(m*n*min(m,n))
Space complexity: O(m*n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua, 148 ms class Solution { public: int maxSideLength(vector<vector<int>>& mat, int threshold) { const int m = mat.size(); const int n = mat[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int y = 1; y <= m; ++y) for (int x = 1; x <= n; ++x) dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1]; auto rangeSum = [&](int x1, int y1, int x2, int y2) { return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1]; }; int ans = 0; for (int y = 1; y <= m; ++y) for (int x = 1; x <= n; ++x) for (int k = 0; y + k <= m && x + k <= n; ++k) { if (rangeSum(x, y, x + k, y + k) > threshold) break; ans = max(ans, k + 1); } return ans; } }; |
Solution 2: Binary Search
Search for the smallest size k that is greater than the threshold, ans = k – 1.
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// Author: Huahua, 116 ms class Solution { public: int maxSideLength(vector<vector<int>>& mat, int threshold) { const int m = mat.size(); const int n = mat[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int y = 1; y <= m; ++y) for (int x = 1; x <= n; ++x) dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1]; auto rangeSum = [&](int x1, int y1, int x2, int y2) { return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1]; }; int ans = 0; for (int y = 1; y <= m; ++y) for (int x = 1; x <= n; ++x) { int l = 0; int r = min(m - y, n - x) + 1; while (l < r) { int m = l + (r - l) / 2; // Find smllest l that > threshold, ans = (l + 1) - 1 if (rangeSum(x, y, x + m, y + m) > threshold) r = m; else l = m + 1; } ans = max(ans, (l + 1) - 1); } return ans; } }; |
Solution 3: Bounded Search
Time complexity: O(m*n + min(m,n))
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// Author: Huahua, 148 ms class Solution { public: int maxSideLength(vector<vector<int>>& mat, int threshold) { const int m = mat.size(); const int n = mat[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int y = 1; y <= m; ++y) for (int x = 1; x <= n; ++x) dp[y][x] = dp[y][x - 1] + dp[y - 1][x] - dp[y - 1][x - 1] + mat[y - 1][x - 1]; auto rangeSum = [&](int x1, int y1, int x2, int y2) { return dp[y2][x2] - dp[y2][x1 - 1] - dp[y1 - 1][x2] + dp[y1 - 1][x1 - 1]; }; int ans = 0; for (int y = 1; y <= m; ++y) for (int x = 1; x <= n; ++x) for (int k = ans; y + k <= m && x + k <= n; ++k) { if (rangeSum(x, y, x + k, y + k) > threshold) break; ans = max(ans, k + 1); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment