求最大子矩阵的大小

题目

给定一个整型矩阵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}为例

image

实质是在一个直方图中求最大的矩形面积。如果能求出以每一根柱子扩展出去的最大矩形，那么最大的矩形就是要求的答案。

而一根柱子可扩展的最大矩形受木桶原理约束，向左最远扩展到第一根小于它的柱子，向右最远扩展到第一根小于它的柱子。

像这种连续的取值，取值只受前后两端影响的情况，可以使用栈来实现。

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