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

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

示例 1:

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

示例 2：

输入： heights = [2,4]
输出： 4

提示：

1 <= heights.length <=10(5)

0 <= heights[i] <= 10(4)

先考虑暴力解法，我们可以把每根柱子当作高，依次找左右两边最多宽为多少，最后取最大值

再去优化怎么去找左右边界

对于左边界，因为我们要找最近的小于自身的柱子，所以对于左边还大的柱子我们没必要记录

想到单调栈，在当前柱子 小于等于 栈顶时才弹出

此时栈顶柱子为最近小于当前柱的，右边界同理

注意栈为空时左边界需记为-1，右边界记为n，可以当成两头各有一个高度最低的虚拟柱子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int largestRectangleArea(vector<int> &heights) {
        int n = heights.size();
        vector<int> left(n);
        vector<int> right(n);
        stack<int> s;
        for (int i = 0; i < n; i++) {
            while (!s.empty() && heights[i] <= heights[s.top()]) {
                s.pop();
            }
            left[i] = s.empty() ? -1 : s.top();
            s.push(i);
        }
        while (!s.empty())
            s.pop();
        for (int i = n - 1; i >= 0; i--) {
            while (!s.empty() && heights[i] <= heights[s.top()]) {
                s.pop();
            }
            right[i] = s.empty() ? n : s.top();
            s.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, heights[i] * (right[i] - left[i] - 1));
        }
        return ans;
    }
};

当我们在计算左边界，弹出栈顶时，这些被弹出的元素说明在 i 之前没有比他们低的元素，也就是i就是离他们最近的比他们低的元素，可以省下一次计算右边界的过程