矩形区域不超过k的最大数值和

给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵内部不大于 k 的最大矩形和。

示例:

输入: matrix = [[1,0,1],[0,-2,3]], k = 2

输出: 2

解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

说明：

1. 矩阵内的矩形区域面积必须大于 0。
2. 如果行数远大于列数，你将如何解答呢？

解题思路：

根据题意，寻找二维数组中所有可以组成的矩形中面积不超过k的最大值，所以必须要求出可能组成的矩形的面积并与k比较求出最终结果。这里为了最终不超时，可以在一下方面进行优化：

1.设置一个数组比较当前列(或者行)下已经扫描过的数的和。

2.设置一个TreeMap，保存当前矩阵长度下，已经扫描过得矩形的面积。同时，TreeMap中有快速查找元素的方法，可以快速查找所找的元素。

1 1 import java.util.TreeSet;
2 2 
3 3 public class Solution {
4 4     public static int maxSumSubmatrix(int[][] matrix, int target) {
5 5         int row = matrix.length;
6 6         if(row==0)
7 7             return 0;
8 8         int col = matrix[0].length;
9 9         if(col==0)
1010             return 0;
1111         int result = Integer.MIN_VALUE;
1212         boolean key= col>row?false:true;
1313         int m = Math.min(row,col);
1414         int n = Math.max(row,col);
1515         //一行一行的找
1616         for(int i=0;i<m;i++){
1717             //找从第i行开始一直到第0行这i+1行的可能组成的矩形长度
1818             int[] array = new int[n];//这个矩阵为了保存每一列上第j行到第i行的和
1919             for(int j=i;j>=0;j--){
2020                 TreeSet<Integer> set = new TreeSet<Integer>();//用来保存当前高度下，长度为从0开始到k位置的矩形的结果。理解set的含义是解决此题的关键。
2121                 set.add(0);
2222                 int sum=0;
2323                 for(int k=0;k<n;k++){
2424                     if(key){
2525                         array[k]+=matrix[k][j];
2626                     }
2727                     else{
2828                         array[k]+=matrix[j][k];
2929                     }
3030                     sum+=array[k];
3131                     /* 因为要满足  （sum-set中的元素）<=target,
3232                      * 而且sum-set中的元素的值要尽可能的大，
3333                      * 所以也就是再求小于等于sum-target中满足条件的元素的最小的一个
3434                      * 正好TreeSet中提供了这个方法ceil()，可以很方便的找出这个元素
3535                      */
3636                     Integer integer = set.ceiling(sum-target);
3737                     if(integer!=null){
3838                         result=Math.max(result, sum-integer);
3939                     }
4040                     set.add(sum);
4141                 }
4242             }
4343         }
4444         return result;
4545     }
4646 }