85. 最大矩形

85. 最大矩形

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0)
            return 0;
        int[] heights = new int[matrix[0].length];
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            max = Math.max(max, largestRectangleArea(heights));
        }
        return max;
    }
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        } else if (len == 1) {
            return heights[0];
        }
        int[] newHeigths = new int[len + 2];
        for (int i = 0; i < heights.length; i++) {
            newHeigths[i + 1] = heights[i];
        }
        heights = newHeigths;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        int area = 0;
        for (int i = 1; i < heights.length; i++) {
            while (heights[i] < heights[stack.peek()]) {
                // 当前遍历到的严格小于栈顶的 
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                area = Math.max(area, width * height);
            }
            stack.push(i);
        }
        return area;
    }
}