题目描述

解题思路

其他解法

参照官解:https://leetcode.cn/problems/maximal-rectangle/solution/zui-da-ju-xing-by-leetcode-solution-bjlu/

单调栈解法

可以直观的看见每一层相当于求一次最大的矩形面积，所以每一层都遍历一遍，使用一个变量记录最大的即可，每一层如何操作参照84.柱状图中最大的矩形的几种做法都可以求！！！直接照搬即可，就是转化一下。

所以本题重要的是表示高度，2次遍历，使用一个一维数组来记录高度。

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int[] height = new int[matrix[0].length];
        int maxSize = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == '1') {
                    height[j] += 1;
                }else {
                    height[j] = 0;
                }
            }
            maxSize = Math.max(largestRectangleArea(height), maxSize);
        }
        return maxSize;
    }
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int size = 0;
        int[] newHeights = new int[heights.length + 2];
        for (int i = 0; i < heights.length; i++) {
            newHeights[i + 1] = heights[i];
        }
        heights = newHeights;
        stack.push(0);
        for (int i = 1; i < heights.length; i++) {
            if (heights[stack.peek()] <= heights[i]) {
                stack.push(i);
            } else if (heights[stack.peek()] > heights[i]) {
                while (heights[stack.peek()] > heights[i]) {
                    int height = heights[stack.peek()];
                    stack.pop();
                    int left = stack.peek();
                    int width = i - left - 1;
                    size = Math.max(height * width, size);
                }
                stack.push(i);
            }
        }
        return size;
    }
}