Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

Tips:

O(n^2)

先进行两层循环，算出在每个点，它上方的height高度。

然后再两层循环，算出每个点的长方形，类似Largest Rectangle in Histogram，算出最大的。

详细：

我们可以从左到右遍历所有bar，并将比栈顶元素小的元素push到一个stack中，stack中总是保持递增的元素的索引，然后当遇到较小的元素后，依次出栈并计算栈中bar能围成的面积，直到栈中元素小于当前元素。

如果当前bar的高度小于栈顶bar，我们pop出栈顶的bar，同时以该bar计算矩形面积。

那么我们如何知道该bar的ln和rn呢？rn铁定就是当前遍历到的bar的索引，而ln则是当前的栈顶bar的索引，因为此时栈顶bar的高度一定小于pop出来的bar的高度。

http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html

Code:

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        if (n == 0) return 0;
        int m = matrix[0].length;
        if (m == 0) return 0;
        int[][] height = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0) {
                    height[i][j] = ((matrix[i][j] == '1') ? 1 : 0);
                }
                else {
                    height[i][j] += ((matrix[i][j] == '1') ? height[i-1][j] + 1 : 0);                    
                }
            }
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            Stack<Integer> S = new Stack<Integer>();  
            for (int j = 0; j < m; j++) {
                while (!S.empty() && height[i][j] < height[i][S.peek()]) {
                    int pos = S.peek();
                    S.pop();
                    answer = Math.max(answer, height[i][pos]*(S.empty()? j : j-S.peek()-1));
                }
                S.push(j);
            }
            while (!S.empty()) {
                int pos = S.peek();
                S.pop();
                answer = Math.max(answer, height[i][pos]*(S.empty()? m : m-S.peek()-1));
            }
        }
        return answer;
    }
}