# 0085. Maximal Rectangle
###### tags: `Leetcode` `Stack` `Hard`
Link: https://leetcode.com/problems/maximal-rectangle/
## 思路
是[1504. Count Submatrices With All Ones](https://hackmd.io/86AP-3gOTmeWP2XtzCr1bg)和[0084. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)的结合体
## Code

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] h = new int[n];
        int ans = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j]=='0') h[j]=0;
                else h[j]++;
            }
            int max = helper(h);
            ans = Math.max(ans, max);
        }
        
        return ans;
    }
    private int helper(int[] heights){
        Stack<Integer> stack = new Stack<>();
        int area = 0;
        for(int i=0; i<heights.length; i++){
            while(!stack.isEmpty() && heights[stack.peek()]>heights[i]){
                int h = heights[stack.pop()];
                int w = i-(stack.isEmpty()?0:(stack.peek()+1));
                area = Math.max(area, h*w);
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int h = heights[stack.pop()];
            int w = heights.length-(stack.isEmpty()?0:stack.peek()+1);
            area = Math.max(area, h*w);
        }
        return area;
    }
}