问题描述 链接到标题

84. 柱状图中最大的矩形 (Hard) 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子 彼此相邻，且宽度为 1 。

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

示例 1:

![](https://assets.leetcode.com/uploads/2021/01/04/histogram .jpg)

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

示例 2：

![](https://assets.leetcode.com/uploads/2021/01/04/histogram -1.jpg)

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

提示：

  • 1 <= heights.length <=10⁵
  • 0 <= heights[i] <= 10⁴

解题思路 链接到标题

本题其实还是求一个连续变长区间的最小值，以及该区间的长度，可以考虑到使用单调栈来解决，至于使用单调递增还是单调递减栈，代入题目中的示例模拟一下就知道了，本题应该使用单调递增栈（栈底到栈顶单调递增）。

在本题中，我们遍历数组，对 nums[i]，找到满足 nums[r] < nums[i] 且 r > i 的最小的 r，记为 ridx，找到满足 nums[l] < nums[i] 且 l < i 的最大的 l，记为 lidx，则 res = max(res, nums[i] * (ridx - lidx - 1))，我们可以利用单调栈在 $O(n)$ 时间内完成求解。

代码 链接到标题 

class Solution {
  public:
    int largestRectangleArea(vector<int> &heights) {
        // 栈底到栈顶单调递增，栈中存储的是索引
        if (heights.size() == 1) {
            return heights[0];
        }
        stack<int> stk;
        int n = heights.size();
        int res = 0;
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && heights[i] < heights[stk.top()]) {
                int h = heights[stk.top()];
                stk.pop();
                if (!stk.empty()) {
                    res = max(res, (i - stk.top() - 1) * h);
                } else {
                    res = max(res, (i)*h);
                }
            }
            stk.push(i);
        }
        int right = stk.top();
        while (!stk.empty()) {
            int h = heights[stk.top()];
            stk.pop();
            if (!stk.empty()) {
                res = max(res, (right - stk.top()) * h);
            } else {
                res = max(res, h * n);
            }
        }
        return res;
    }
};