题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
样例
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10。
输入：heights = [2,4]
输出：4
限制
1 <= heights.length <= 10^50 <= heights[i] <= 10^4
算法
(单调栈) $O(n)$
- 此题的本质是找到每个柱形条左侧第一个比自己低或相等，以及右侧第一个严格比自己低的矩形条，然后用宽度乘上当前柱形条的高度作为备选答案。
- 解决此类问题的经典做法是单调栈，维护一个单调递增的栈，如果当前柱形条
i的高度比栈顶要低，则栈顶元素cur出栈。出栈后，cur右侧第一个严格比自己低的柱形条就是i，左侧第一个比自己低或相等的柱形条是当前栈中的top。不断出栈直到栈为空或者柱形条i不再比top低。 - 满足 2 之后，当前矩形条
i进栈。
时间复杂度
- 每个元素最多进栈一次，出栈一次，故时间复杂度为 $O(n)$。
空间复杂度
- 需要额外 $O(n)$ 的空间存储栈。
C++ 代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size(), ans = 0;
heights.push_back(-1);
// 为了算法书写方便，在数组末尾添加高度 -1
// 这会使得栈中所有数字在最后出栈。
stack<int> st;
for (int i = 0; i <= n; i++) {
while (!st.empty() && heights[i] < heights[st.top()]) {
int cur = st.top();
st.pop();
if (st.empty())
ans = max(ans, heights[cur] * i);
else
ans = max(ans, heights[cur]
* (i - st.top() - 1));
}
st.push(i);
}
return ans;
}
};
“此题的本质是找到每个柱形条左边和右边最近的比自己低的矩形条，然后用宽度乘上当前柱形条的高度作为备选答案” 我终于参透了本质！！
左边第一个比它低的柱形条是当前栈中的 top,此话应该为左边第一个比它低或高度相等的柱形条是当前栈中的 top
已修正
点赞，厉害！
我觉得这几行还可以稍微优化一下
right = i
left = st[-1] if st else -1
ans = max(ans, heights[cur] * (right - left - 1))
可能更简洁一些
left = st[-1] if st else -1
这句啥意思，没看懂
我是用Python写的，-1代表最后一个元素（最经刚刚学会看通知。。。，抱歉回复晚了）
懂了，谢谢
这比视频里面更节省空间了啊
惊叹👍
我只能看懂wzc老师写的题解 真的 别的人不是错别字就是讲话我听不懂
y老师说话我也听不懂 呜呜呜
我也觉得hhh
因人而异吧，我只是多提供一种思路，集思广益才是最好的哈
嗯嗯，感谢大佬的题解呀，学到了很多～
应该这么理解，如果是一个单增序列，我们怎么求他的最大值，宽度为1最大的矩形的就是最右边的一个柱形条，宽度为2的最大的矩形就是最右边两个柱形条，依次计算，这样我们就算出了每个宽度下的最大值，是这样得到我们最后的最大值，所以我们这里维护一个单增栈
赞啊～要是可以收藏mark就好啦
膜拜大佬
同时找到左边和右边比自己_低_的值，很惊艳，我自己试了一下，
push_back(-1)真的很方便，赞！请问如果我想找到左边和右边比自己_高_的矩形条，该在heights添加一个什么常数呢？一般
INT_MAX就可以，根据题目情况来定。好的 感谢
赞。
此题的本质是找到每个柱形条左边和右边最近的比自己低的矩形条，然后用宽度乘上当前柱形条的高度作为备选答案。终于算是看明白了，好多细节的地方容易写错，比如stack 存的是索引，stack 存的是索引，stack 存的是索引。
写着写着就把它当成那个value 了。
https://www.youtube.com/watch?v=KkJrGxuQtYo
很好的讲解视频
大佬，借个VPN
histogram 里面会有一样高的bar吗？遇到这种情况又应该怎么处理呢？
如果遇到一样高的bar， 比如[2,1,6,6,6,2]的话，到最后一个6的时候，stack 里面的是[1,6,6,6], 当i 等于5，就是最后一个元素2的时候，程序会进到while 循环，然后是三个6依次从stack 里往外跳，这个时候程序里的i 是固定的，而stack.top()分别是4，3，2，程序会计算（5-4-1）6， （5-3-1）6， （5-2-1）*6， 即index 5 和index 4，3，2 之间的矩形面积
找到每个柱形条左边和右边最近的比自己低的矩形条，然后用宽度乘上当前柱形条的高度作为备选答案。
这句话感觉又无法理解了，我的intuition是：难道不是找到左边或者右边比自己高的矩形条，然后乘以当前矩形条的高度作为备选答案么？
这个当前的柱形高度应该是值得低的矩阵条的高度
单调栈的用法有什么规律么？感觉蛮有用的样子，要不要有空总结一下？嘿嘿
哇，又是单调栈！！