85.最大矩形

题目描述

题解

单调栈

这道题可以完美使用上一道题的方法. 上一道题的场景是柱状图的最大矩形, 这道题编程了二维数组. 如何将二维数组转化为柱状图的形式成了本题的关键.

遍历每一行的数组, 那么正在遍历的这一行与上面的所有行就可以当做是柱状图.

如果某位置字符是1, 往上有多少连续的1 就是该位置的高度, 如果某位置为0, 不管上面有多少1 该位置的高度都为0.

就这样求出每一行作为横轴的柱状图的最大矩形面积.

代码中的maxArea()方法就是84题的代码.

public class lc85 {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0){
            return 0;
        }
        int[] rowHeight = new int[matrix[0].length];
        int res = 0;

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                rowHeight[j] = matrix[i][j] == '0' ? 0 : rowHeight[j] + 1;
            }
            res = Math.max(res, maxArea(rowHeight));
        }

        return res;
    }


    public int maxArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0;
        stack.push(-1);

        for (int i = 0; i < heights.length; i++) {
            if (stack.peek() == -1 || heights[i] > heights[stack.peek()]) {
                stack.push(i);
            } else {
                while (stack.size() > 1 && heights[i] < heights[stack.peek()]) {
                    int temp = stack.pop();
                    res = Math.max(res, heights[temp] * (i - stack.peek() - 1));
                }
                stack.push(i);
            }
        }

        while (stack.size() > 1) {
            int temp = stack.pop();
            res = Math.max(res, heights[temp] * (heights.length - stack.peek() - 1));
        }

        return res;

    }
}