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

[lxw124]

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。

[lxw124]

首先要计算每个矩阵中元素到左上角所围起来的元素加起来的和，然后再计算围起来的正方形的阈值小于threshold中数最大的那个

var maxSideLength = function(mat, threshold) {
    var dp=new Array(mat.length+1)//定义二维数组，计算元素的和
    for(var i=0;i<dp.length;i++){
        dp[i]=new Array(mat[0].length+1).fill(0)
    }
    for(var i=1;i<=dp.length-1;i++){
        for(var j=1;j<=dp[0].length-1;j++){
            dp[i][j]=mat[i-1][j-1]+dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]
        }
    }
    var res=0;
    for(var k=1;k<=Math.min(mat.length,mat[0].length);k++){
        for(var i=1;i<=mat.length;i++){
            for(var j=1;j<=mat[0].length;j++){
                if(i<k||j<k){
                    continue
                }
                let temp=dp[i][j]-dp[i-k][j]-dp[i][j-k]+dp[i-k][j-k]
                if(temp<=threshold){
                    res=Math.max(res,k)
                }
            }
        }
    }
    return res;

};