题目链接

Leetcode.1292 元素和小于等于阈值的正方形的最大边长 Rating ： 1735

题目描述

给你一个大小为 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，如图所示。

示例 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

提示：

• m == mat.length
• n == mat[i].length
• 1<=m,n<=3001 <= m, n <= 3001<=m,n<=300
• 0<=mat[i][j]<=1040 <= mat[i][j] <= 10^40<=mat[i][j]<=104
• 0<=threshold<=1050 <= threshold <= 10^50<=threshold<=105

解法：二维前缀和 + 二分

首先我们将原矩阵转换为 二维前缀和矩阵s。

转换公式 ： s(i,j)=s(i−1,j)+s(i,j−1)−s(i−1,j−1)+mat(i−1,j−1)s(i,j) = s(i-1,j) + s(i,j-1) - s(i-1,j-1) + mat(i-1,j-1)s(i,j)=s(i−1,j)+s(i,j−1)−s(i−1,j−1)+mat(i−1,j−1)

接着我们再 二分边长 k，左边界 l = 1，右边界 r = min(m , n)（m和 n分别是mat的行数和列数）。

如果当前矩阵 mat中能找出边长为 k的正方形，即 l = k；否则 r = k - 1。

对于终点为 (i , j)，我们计算边长为 k的总和公式为 sum=s(i,j)−s(i−k,j)−s(i,j−k)+s(i−k,j−k)sum = s(i,j) - s(i-k,j) - s(i,j-k) + s(i-k,j-k)sum=s(i,j)−s(i−k,j)−s(i,j−k)+s(i−k,j−k)

时间复杂度： O(m∗n∗log(min(m,n))O(m * n *log(min(m,n))O(m∗n∗log(min(m,n))

C++代码：

class Solution {
public:int maxSideLength(vector>& mat, int threshold) {int m = mat.size() , n = mat[0].size();vector> s(m+1,vector(n + 1));for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + mat[i-1][j-1];}}int l = 0 , r = min(m,n);while(l < r){int k = (l + r + 1)/2;bool ok = false;for(int i = k;i <= m;i++){for(int j = k;j <= n;j++){int area = s[i][j] - s[i][j-k] - s[i-k][j] + s[i-k][j-k];if(area <= threshold){ok = true;break;}}}if(ok) l = k;else r = k - 1;}return r;}
};