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;
}
}