问题描述
84. 柱状图中最大的矩形 (Hard) 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子 彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： 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;
}
};