Maximum Side Length of a Square with Sum Less than or Equal to Threshold

给一个2d数组, 给一个数threshold. 返回最大的square的边长, 能让里面的数字和等于或者小于 threshold. 这个题主要考察presum的范围理解, 我们用presum的时候,因为扫描数组是从左往右从上到下, 所以我们想用squares的范围的时候, 需要减去重复的部分. 比如, sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + mat[i][j]; 而不能单纯的sum[i+1][j+1] + mat[i][j] 同理, 当我们检查是否有新的max的时候, 也是用这个方法. 我看到答案里面有别的做法, 比如用二分搜索+测试, 我觉得没必要, 因为复杂度不可能少于O(M*N), 因为不看到最后一个, 怎么知道是不是有可能有最大的square.

class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int[][] sum = new int[mat.length+1][mat[0].length+1];
        int max = 0;
        
        for(int i = 0; i < mat.length; i++) {
            for(int j = 0; j < mat[0].length; j++) {
                //update sum
                sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + mat[i][j];
                //check sum[i+1][j+1] whether it is the new max
                if(max < i + 1 && max < j + 1) {
                    if(sum[i+1][j+1] - sum[i-max][j+1] - sum[i+1][j-max] + sum[i-max][j-max] <= threshold) {
                        max ++;
                    }
                }
            }
        }
        
        return max;
    }
}