vivo提前批面试题，比较难。

这个是在LeetCode的评论区看到的一条留言，我们来看下这道题。

问题描述

来源：LeetCode第84题

难度：困难

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中灰色区域，面积为 10

单调栈解决

这题让求的是柱状图能勾勒出来的最大矩形面积，我们前面刚讲过笛卡尔树图文详解，前面使用的是笛卡尔树，如果对笛卡尔树比较熟悉的话，这题非常简单。除了笛卡尔树，我们还可以使用另外一种解决方式，单调栈。

因为勾勒出来的最大矩形面积高度肯定是其中某一个柱子的高度，一种方式就是以每一个柱子高度为矩形的高度往两边扫描，但这样效率不是很好。这里我们就可以使用单调栈，单调栈存储的是元素的下标，下标对应的值从栈底到栈顶是单调递增的。

遍历数组的时候，如果当前元素的值大于等于栈顶元素所对应的值，就把当前元素的下标添加到栈中。如下图，当遍历到前4个元素的时候，因为都是后面一个比前面一个大，所以都压栈，压入的是元素下标，不是元素的值。

如果当前元素的值小于栈顶元素，说明栈顶元素遇到了右边比他小的，那么这个栈顶元素左边比他小的是哪个呢？就是他在栈中的下一个元素（也有可能相等，但不影响后面的计算），也就是栈顶元素出栈之后新的栈顶元素。当我们知道一个柱子左边和右边比他小的，就可以计算以当前柱子为矩形高度所能勾勒出来的最大矩形了。比如上面的图中当指针指向 2 的时候，我们来看下计算步骤。

这里要注意一点的是数组中的第一个元素前面是没有值的，最后一个元素后面也是没有值的，所以我们可以把数组的前面和后面分别添加一个 0 。

public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();// 栈底到栈顶是递增的
    // 第一个柱子的下标是0，默认他前面一个是-1。
    stack.push(-1);
    int max = 0;// 记录最大面积
    for (int i = 0; i <= heights.length; i++) {
        // 当前柱子的高度，如果i == heights.length，表示没有柱子，高度为0。
        int curHeight = i == heights.length ? 0 : heights[i];
        // 如果当前柱子的高度小于栈顶元素所对应柱子的高度，栈顶元素出栈，计算面积。
        while (stack.size() > 1 && curHeight < heights[stack.peek()]) {
            int h = heights[stack.pop()];// 出栈的柱子高度
            int area = (i - 1 - stack.peek()) * h;// 计算面积
            max = Math.max(max, area);// 保存最大面积
        }
        stack.push(i);// 当前柱子的下标入栈
    }
    return max;// 返回最大面积。
}