题目链接
给定 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

思路

暴力求解

依次遍历每个高度，假设当前高度 hi 为勾勒出的矩形高度，只需要向左和向右分别查找第一个小于 hi 的柱子分别记为 left_i, right_i，则以 hi 为矩形高度的最大面积为 (right_i - left_i -1) * hi，每个元素的查找复杂度是 O(n)，总复杂度为 O(n^2)，n <= 10^5，肯定超时。

单调栈

优化的思路是对第 i 个元素（高度为 hi) 向左或向右快速的找出第一个比它小的元素。引入单调栈算法计算每个元素向左第一个比它小的元素下标位置，记为 res 数组，其中 res[i] = { 向左第一个小于 h[i] 的元素下标 }：
引入一个栈 st，记录元素的下标。依次遍历高度数组中，每个元素入栈前，从栈顶开始弹出栈中所有对应值大于或等于当前元素的下标。

• 如果当前栈为空，表示没有小于当前元素的其他元素，标记 res[i] = -1
• 如果栈不为空，表示栈顶元素为第一个小于当前元素的下标，标记 res[i] = st[top]

最后入栈该元素。从上述操作可知，栈中的元素始终保持为递增（因而称为单调栈）。
单调栈算法在 O(n) 时间内求出了所有元素向左第一个比它小的元素下标位置。

因而上述计算矩形的面积思路优化为：

• 单调栈计算每个高度向左的第一个小于当前高度的位置，记为 left 数组。
• 单调栈计算每个高度向右的第一个小于当前高度的位置（逆序计算向左的即可），记为 right 数组。
• 每个高度对应的最大面积为 (right[i] - left[i] - 1) * height[i]，计算所有高度的最大面积即为结果。
  总的复杂度为 O(n)，问题解决。

代码

class Solution {
public:
    vector<int> solve(vector<int>& heights, bool reverse) {
        int len = heights.size();
        vector<int> res(len + 1, 0);
        int st[len + 1];
        int top = -1;

        int begin = 0;
        int end = len;
        int step = 1;
        int out_ind = -1;
        if (reverse) {
            begin = len - 1;
            end = -1;
            step = -1;
            out_ind = len;
        }

        // 单调栈，查找往左第一个小于当前元素的元素
        for (int i = begin; i != end; i += step) {
            if (top == -1) {
                st[++top] = i;
                res[i] = out_ind;
            } else {
                while(top != -1 && heights[st[top]] >= heights[i]) {
                    --top;
                }

                if (top == -1) {
                    res[i] = out_ind;
                } else {
                    res[i] = st[top];
                }
                st[++top] = i;
            }
        }

        return res;
    }

    int largestRectangleArea(vector<int>& heights) {
        vector<int> res1 = solve(heights, false);
        vector<int> res2 = solve(heights, true);
        int res = 0;
        for (int i = 0; i < heights.size(); i ++) {
            // cout << i << " " << res1[i] << " " << res2[i] << endl;
            res = max(res, heights[i] * (res2[i] - res1[i] - 1));
        }

        return res;
    }
};