1. 題目

給你一個(gè)大小為 m x n 的矩陣 mat 和一個(gè)整數(shù)閾值 threshold。

請你返回元素總和小于或等于閾值的正方形區(qū)域的最大邊長；
如果沒有這樣的正方形區(qū)域，則返回 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，如圖所示。示例 2： 輸入：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 輸出：0示例 3： 輸入：mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6 輸出：3示例 4： 輸入：mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184 輸出：2提示： 1 <= m, n <= 300 m == mat.length n == mat[i].length 0 <= mat[i][j] <= 10000 0 <= threshold <= 10^5

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 先求出左上角（0,0）到任意位置組成的矩形的和
• 然后遍歷所有的 左上頂點(diǎn)，再遍歷正方形的邊長
• 時(shí)間復(fù)雜度 $O(mn?min(m,n))$

class Solution { public:int maxSideLength(vector<vector<int>>& mat, int threshold) {int m = mat.size(), n = mat[0].size(), i, j, maxlen = 0, len = 0;vector<vector<int>> sum(m,vector<int>(n,0));//先求第一行、第一列的前綴和for(j = 0; j < n; ++j)sum[0][j] = (j > 0 ? sum[0][j-1] : 0) + mat[0][j];//注意加括號for(i = 1; i < m; ++i)sum[i][0] = sum[i-1][0] + mat[i][0];//剩余位置的前綴和for(i = 1; i < m; ++i)for(j = 1; j < n; ++j)sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]+mat[i][j];int ni, nj, sumofarea;//遍歷左上角位置for(i = 0; i < m; ++i)for(j = 0; j < n; ++j)for(len = 1; len <= min(m,n); ++len){ //遍歷正方形邊長ni = i+len-1;//右下角nj = j+len-1;if(ni < m && nj < n){sumofarea = sum[ni][nj]-(i>0?sum[i-1][nj]:0)-(j>0?sum[ni][j-1]:0)+((i>0&&j>0) ? sum[i-1][j-1] : 0);//由前綴和推出正方形的和if(sumofarea <= threshold){maxlen = max(maxlen, len);if(maxlen == min(m,n))return maxlen;}}elsebreak;}return maxlen;} };

1104 ms 22.6 MB

• 優(yōu)化，下一個(gè)頂點(diǎn)，遍歷的長度從maxlen+1開始找
• 和是增大的，一旦大于閾值就不必往下找了
• 這種解法的時(shí)間復(fù)雜度為 $O(mn)$，可以參考官方題解分析，比最內(nèi)層循環(huán)采用二分查找的方式$O(mn\log (min(m,n))$更優(yōu)

class Solution { public:int maxSideLength(vector<vector<int>>& mat, int threshold) {int m = mat.size(), n = mat[0].size(), i, j, maxlen = 0, len = 0;vector<vector<int>> sum(m,vector<int>(n,0));for(j = 0; j < n; ++j)sum[0][j] = (j > 0 ? sum[0][j-1] : 0) + mat[0][j];for(i = 1; i < m; ++i)sum[i][0] = sum[i-1][0] + mat[i][0];for(i = 1; i < m; ++i)for(j = 1; j < n; ++j)sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]+mat[i][j];int ni, nj, sumofarea;for(i = 0; i < m; ++i)for(j = 0; j < n; ++j)for(len = maxlen+1; len <= min(m,n); ++len){ni = i+len-1;nj = j+len-1;if(ni < m && nj < n && sum[ni][nj]-(i>0?sum[i-1][nj]:0)-(j>0?sum[ni][j-1]:0)+(i>0&&j>0 ? sum[i-1][j-1] : 0) <= threshold){maxlen = max(maxlen, len);if(maxlen == min(m,n))return maxlen;}elsebreak;}return maxlen;} };

176 ms 22.5 MB

python3 解答

class Solution:# py3def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:m, n = len(mat), len(mat[0])maxlen = 0prefixsum = [[0]*n for _ in range(m)]prefixsum[0][0] = mat[0][0]for j in range(1,n):prefixsum[0][j] = prefixsum[0][j-1]+mat[0][j]for i in range(1,m):prefixsum[i][0] = prefixsum[i-1][0]+mat[i][0]for i in range(1,m):for j in range(1,n):prefixsum[i][j] = prefixsum[i-1][j]+prefixsum[i][j-1]-prefixsum[i-1][j-1]+mat[i][j]for i in range(m):for j in range(n):length = maxlen+1while length <= min(m,n):ni = i+length-1nj = j+length-1if ni<m and nj<n and prefixsum[ni][nj]-(prefixsum[i-1][nj] if i > 0 else 0)-(prefixsum[ni][j-1] if j > 0 else 0)+(prefixsum[i-1][j-1] if i>0 and j>0 else 0) <= threshold:maxlen = max(maxlen, length)if maxlen == min(m,n):return maxlenelse:breaklength += 1return maxlen

1092 ms 19.3 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1292. 元素和小于等于阈值的正方形的最大边长（DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。