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

给你一个大小为 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

示例 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 1074. 元素和为目标值的子矩阵数量–map+前缀和

AC代码

class Solution {
public:
    int dp[305][305];
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        memset(dp,0,sizeof(dp));
        for(int i=0;i<mat.size();i++)
        {
            for(int j=0;j<mat[i].size();j++)
            {
                dp[i+1][j+1]=dp[i][j+1]+mat[i][j];
            }
        }
        int d=0;
        for(int i1=1;i1<=mat.size();i1++)
        {
            int ans=0;
            for(int i2=i1+d;i2<=mat.size();i2++)//只找比当前的宽度要大的正方形
            {
                if(i2-i1+1>mat[0].size())break;//特判
                for(int j=1;j<=i2-i1+1;j++)//当前正方形宽度
                {
                    ans+=(dp[i2][j]-dp[i1-1][j]);//累计元素和
                }
                if(ans<=threshold)
                {
                    d=i2-i1+1;
                }
                for(int j=i2-i1+2;j<=mat[0].size();j++)
                {
                    ans-=(dp[i2][j-(i2-i1+1)]-dp[i1-1][j-(i2-i1+1)]);
                    ans+=(dp[i2][j]-dp[i1-1][j]);
                   // cout<<i1<<" "<<i2<<" "<<j<<" "<<ans<<endl;
                    if(ans<=threshold)
                    {
                        d=i2-i1+1;
                        break;
                    }
                }
            }
        }
        return d;
    }
};