85.Maximal Rectangle

和84题同样思路，O(n^2)

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        if(n < 1)
            return 0;
        int m = matrix[0].length;
        int[] height = new int[m];
        for(int i = 0;  i < m; i++){
            if(matrix[0][i] == '1'){
                height[i] = 1;
            }
            else{
                height[i] = 0;
            }
        }
        int ans = maxRecPerLine(height);
        for(int i = 1; i < n ; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j] == '1'){
                    height[j] = 1 + height[j];
                }
                else{
                    height[j] = 0;
                }
            }
            ans = Math.max(ans, maxRecPerLine(height));
        }
        return ans;
    }
    public int maxRecPerLine(int[] height){
        Stack<Integer> s = new Stack<>();
        s.push(-1);
        int ans = 0;
        int n = height.length;
        for(int i = 0; i < n; i++){
            while(s.peek() != -1 && height[s.peek()] > height[i]){
                ans = Math.max(ans, height[s.pop()] * (i - 1 - s.peek())); 
            }
            s.push(i);
        }
        while(s.peek() != -1){
            ans  = Math.max(ans, height[s.pop()] * (n - 1 - s.peek()));
        }
        return ans;
    }
}