题目
给定一个整型矩阵map， 其中的值只有0 和 1 两种， 求其中全是1 的所有矩形区域中， 最大的矩形区域为1的数量。
例如：
1 0 1 1
1 1 1 1
1 1 1 0
其中，最大的矩形区域有6个1，所以返回6 。
分析
若矩阵大小为O（MN），则时间复杂度为O（MN）的解法为：
1.对矩阵的每一行进行切割，统计以当前行为底的情况下，每个位置往上1的数量。(若当前位置为1，则统计从当前位置开始向上连续1的数量；若当前位置为0，则数量计为0）
例如map=1 0 1 1
1 1 1 1
1 1 1 0
第1行height={1，0，1，1}
第2行height={2，1，2，2}
第3行height={3，2，3，0}
2.计算每一行为底的情况下，最大的矩形是什么。
以height={3，2，3，0}为例
实质是在一个直方图中求最大的矩形面积。如果能求出以每一根柱子扩展出去的最大矩形，那么最大的矩形就是要求的答案。
而一根柱子可扩展的最大矩形受木桶原理约束，向左最远扩展到第一根小于它的柱子，向右最远扩展到第一根小于它的柱子。
像这种连续的取值，取值只受前后两端影响的情况，可以使用栈来实现。
以height={3，4，5，4，3，6}为例，我们知道一根柱子的最大矩形的面积只受左右两端影响，于是我们要求的就是每一根柱子的左右两端位置。
我们从左往右遍历height，栈为空压入3，此时柱子height[0] 的左端已经确定，只需要确定柱子的右端。由此我们得到两个关键逻辑：
1.只有当前i位置的值heigh[i]大于当前栈顶位置所代表的值（height[stack.peek()]，则i位置才可以压入stack
2.如果当前i位置的值heigh[i]小于或等于当前栈顶位置所代表的值（height[stack.peek()]，则把栈中存的位置不断弹出，直到某一个栈顶所代表的值小于height[i]，再把i位置压入
当height[i]小于height[stack.peek()]柱子的右端位置也确定了，这个很容易理解。但是height[i]等于height[stack.peek()]时右端位置并没有确定，在这种情况下，height[i]与height[stack.peek()]所能扩到的左右端位置必定相同，于是我们可以将height[stack.peek()]出栈，通过height[i]来求得二者的最大面积。
最大矩形面积为（i-k-1)*height[j]，其中i为当前遍历到的height位置，k为栈顶位置，j为刚出栈的柱子位置。
注意，栈为空时左端位置可以记为-1，height遍历完时右端位置可以记为height.length。
public class MaxRecSize {
public int getMaxRecSize(int[][] map) {
if (map == null || map.length == 0 || map[0].length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int[] height = new int[map[0].length];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
height[j] = map[i][j] > 0 ? height[j] + 1 : 0;
}
max = Math.max(max, getMaxRexSizeFromBottom(height));
}
return max;
}
public int getMaxRexSizeFromBottom(int[] height) {
if(height == null || height.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
Stack<Integer> s = new Stack<Integer>();
for (int i = 0; i < height.length; i++) {
while (!s.isEmpty() && height[s.peek()] >= height[i]) {
int current = s.pop();
int top = s.isEmpty() ? -1 : s.peek();
max = Math.max(max, (i - top - 1) * height[current]);
}
s.push(i);
}
while (!s.isEmpty()) {
int current = s.pop();
int top = s.isEmpty() ? -1 : s.peek();
max = Math.max(max, (height.length - top - 1) * height[current]);
}
return max;
}
}
