给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
单调栈
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int result = 0;
stack<int> st;
vector<int> res(heights.size(),heights.size());
//正序寻找最近的比自己小的值
for (int i = 0; i < heights.size(); ++i) {
while (!st.empty() && heights[i] < heights[st.top()]) {
res[st.top()] = i;
st.pop();
}
st.push(i);
}
stack<int> st2;
vector<int> res2(heights.size(),-1);
//逆序寻找最近的比自己小的值
for (int i = heights.size() - 1; i >= 0; --i) {
while (!st2.empty() && heights[i] < heights[st2.top()]) {
res2[st2.top()] = i;
st2.pop();
}
st2.push(i);
}
for (int i = 0; i < heights.size(); ++i) {
int tmp = (abs(res2[i] - res[i]) - 1) * heights[i];
result = max(result, tmp);
//cout << tmp << " ";
}
return result;
}
};
原文：https://www.cnblogs.com/aaronwell/p/14603894.html