Maximal Rectangle

给一个2d数组, 里面是0和1. 返回最大的全是1的矩形. 这个题和柱状图的最大矩形是一个解法.用largest方法找到一个数组上最大的矩形.

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0)
            return 0;
        int[] hist = new int[matrix[0].length];
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;
        for(int i = 0 ; i < m; i++) {
            for(int j = 0 ; j < n; j++) {
                if(matrix[i][j] == '1')
                    hist[j] ++;
                else
                    hist[j] = 0;
            }
            max = Math.max(max, largest(hist));
        }
        return max;
    }
    public int largest(int[] height) {
        if(height == null || height.length == 0)
            return 0;
        int max = 0;
        Stack<Integer> st = new Stack<Integer>();
        for(int i = 0 ; i <= height.length; i++) {
            int cur = (i == height.length)? 0:height[i];
            if(st.empty() || cur > height[st.peek()])
                st.push(i);
            else{
                int tmp = st.pop();
                max = Math.max(max, height[tmp] *(st.empty()? i : i - st.peek() - 1) );
                i--;
            }
        }
        return max;
    }
}