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

Link

Solution

原本設計的binary search形式只能找到滿足條件的最小值，而且假設n滿足條件n+1,n+2... 都會滿足

int left = 0, right = arr.length;

while( left < right ){
    int mid = left + (right-left)/2;
    if(condition(mid)){
        right = mid;
    }else{
        left = mid+1;
    }
}
return left;

但這個case則是相反，假設n滿足條件，則是n-1,n-2..都會滿足，這種case要用下列這種形式

 int left = 0;
int right = arr.length;

while(right >= left){
    int mid = left + (right-left)/2;
    
    if(condition(mid)){
        left = mid+1;
    }
    else{
        right = mid-1;
    }
}
return right;

  int m, n;
    public int maxSideLength(int[][] mat, int threshold) {
        m = mat.length;
        n = mat[0].length;
        
        int[][] sum = new int[m+1][n+1];
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mat[i-1][j-1];
            }
        }
        int left = 0;
        int right = Math.min(m,n);
        
        while(right >= left){
            int mid = left + (right-left)/2;
            
            if(isExistedSqaure(sum, mid, threshold)){
                left = mid+1;
            }
            else{
                right = mid-1;
            }
        }
        return right; 
       
    }
    
    public boolean isExistedSqaure(int[][] sum, int len, int threshold){
        for(int i = len; i <= m; i++){
            for(int j = len; j <= n; j++){
                int curSum = sum[i][j] - sum[i-len][j] - sum[i][j-len] + sum[i-len][j-len];  
                if(curSum <= threshold) return true;
            }
        }
        return false;
        
    }