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.

如果一行一行的扫描matrix，那么每一行按照largest rectangle history方法求area即可。写了一个getMax函数来得到当前行的最大值，这个getmax函数就是largets rectagle historym 的方法题的解法

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
        int res = 0;
        int[] height = new int[matrix[0].length];
        for(int i = 0; i < matrix[0].length; i++){
            height[i] = matrix[0][i] == '0' ? 0 : 1;
        }
        res = getMax(height);
        for(int i = 1; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == '0') height[j] = 0;
                else{
                    height[j] += 1;
                }
            }
            res = Math.max(res, getMax(height));
        }
        return res;
    }
    public int getMax(int[] height){
        if(height == null || height.length == 0 ) return 0;
        Stack<Integer> stack = new Stack<Integer>();
        int res = 0;
        for(int i = 0; i <= height.length; i++){
            int curt = (i == height.length) ? -1 : height[i];
            while(!stack.isEmpty() && curt <= height[stack.peek()]){
                int index = stack.pop();
                int h = height[index];
                int w = (stack.isEmpty()) ? i : i - stack.peek() - 1;
                res = Math.max(res, h * w);
            }
            stack.push(i);
        }
        return res;
    }
}