?LeetCode刷題實(shí)戰(zhàn)363：矩形區(qū)域不超過 K 的最大數(shù)值和

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

imppublic class Solution {
    public static int maxSumSubmatrix(int[][] matrix, int target) {
        int row = matrix.length;
        if(row==0)
            return 0;
        int col = matrix[0].length;
        if(col==0)
            return 0;
        int result = Integer.MIN_VALUE;
        boolean key= col>row?false:true;
        int m = Math.min(row,col);
        int n = Math.max(row,col);
        //一行一行的找
        for(int i=0;i<m;i++){
            //找從第i行開始一直到第0行這i+1行的可能組成的矩形長度
            int[] array = new int[n];//這個(gè)矩陣為了保存每一列上第j行到第i行的和
            for(int j=i;j>=0;j--){
                TreeSet<Integer> set = new TreeSet<Integer>();//用來保存當(dāng)前高度下，長度為從0開始到k位置的矩形的結(jié)果。理解set的含義是解決此題的關(guān)鍵。
                set.add(0);
                int sum=0;
                for(int k=0;k<n;k++){
                    if(key){
                        array[k]+=matrix[k][j];
                    }
                    else{
                        array[k]+=matrix[j][k];
                    }
                    sum+=array[k];
                    /* 因?yàn)橐獫M足 （sum-set中的元素）<=target,
                     * 而且sum-set中的元素的值要盡可能的大，
                     * 所以也就是再求小于等于sum-target中滿足條件的元素的最小的一個(gè)
                     * 正好TreeSet中提供了這個(gè)方法ceil()，可以很方便的找出這個(gè)元素
                     */
                    Integer integer = set.ceiling(sum-target);
                    if(integer!=null){
                        result=Math.max(result, sum-integer);
                    }
                    set.add(sum);
                }
            }
        }
        return result;
    }
}