题目描述

题解

单调栈

这道题的暴力解法就是, 遍历每个柱子, 然后从该柱子开始往两边扩散, 直到找出最近的比它小的柱子. 那么该柱子能获得的最大面积就是

1	square = height[i] * (right - left - 1);

例如实例图中的高度为5的柱子, 左边第一个比它小的柱子下标为1, 右边第一个比它小的柱子下标为4, 那么该柱子构成的最大面积为

5 * (4 - 1 -1 ) = 10.

如果采用循环遍历左右边界的话, 时间复杂度是N^2, 我们使用 单调栈 的方法在一次遍历中就确定出每个柱子的左右边界.

在遍历整个数组时, 如果当前高度大于栈顶的数值, 就说明当前栈顶的柱子就是它左边第一个比它小的柱子, 将其作为左边界记录下来, 将其压入栈中, 成为新的栈顶.

如果当前柱子高度小于栈顶的数值, 说明该柱子的其左边界不在栈顶, 就循环弹出, 直到栈顶元素比它小, 将其作为左边界记录下来, 再将当前柱子压入栈中, 成为新的栈顶.

这样遍历一次以后, 每个柱子的左边界就确定下来了. 按照同样的方法从右至左再来一遍就可以确定出右边界.

class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];

        for (int i = 0; i < heights.length; i++) {

            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                stack.pop();
            }

            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        for (int i = heights.length - 1; i >= 0; i--) {

            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }

            right[i] = stack.isEmpty() ? heights.length : stack.peek();
            stack.push(i);
        }

        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }
        return res;
        
    }
}

单调栈+优化

上面的方法需要遍历两次数组, 其实右边界不需要再额外遍历才能求出, 当栈顶元素需要弹出时, 就已经说明它是栈中所有比它大的元素的右边界了.

每个柱子入栈后, 其下面的柱子就是它的左边界.

class Solution {
    public int largestRectangleArea(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;

    }
}