# 84. 柱状图中最大的矩形 (Hard)

## 问题描述
[84. 柱状图中最大的矩形 (Hard)](https://leetcode.cn/problems/largest-rectangle-in-histogram/)
给定 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)$ 时间内完成求解。

## 代码
```cpp
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;
    }
};
```