leetcode 题解 84. Largest Rectangle in Histogram （单调栈的应用们）
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height =
[2,1,5,6,2,3].The largest rectangle is shown in the shaded area, which has area =
10unit.
图片我就不贴了，大家自己脑补就好。
这个问题是归类在stack题目分类下了。一开始我怎么看是怎么觉得这应该是一个类似于线段树的题目的，区间内求最小值乘以区间长度这样？
后来我发现discuss区有几位大佬都是用栈去解决这个问题的，这就激发了我的好奇心，搜索了一番，发现了一种名为“单调栈”的套路。
单调栈，顾名思义，就是栈维持某种单调性，比如递增、递减、递不增、递不减。那么加入我有一个数组，要压栈，要实现这种单调性，怎么破？有以下两种思路：
- 当要压栈的数不满足规定的单调性，就不把这个数压栈。
- 当压栈的数破坏了单调性，就不停地弹出栈中的元素，直到新数字压进去也不会破坏单调性为止。这么说可能有点绕，举个例子，比如我要在一个单调递增的栈中压入新数字3，而栈顶元素是4，此时直接压入3就不是单调栈了，这时候我就弹出4，看新的栈顶元素，以此类推，直到栈顶元素小于3为止。
方法一按下不表，单看方法二，还是有很多用途的。最大的用途可以总结为：我可以找到数组中每一个特定数字后面会满足/破坏某种条件的第一个元素。
来，请听题：
给定一个数组，输出一个与这个数组等长的数组作为结果。输出的数组中的元素为，对于原数组中的第i个元素，需要往后移动多少个单位，才能找到第一个比他大的数字。如果没有比他大的元素，该位输出-1
这个时候，我们可以分析这个问题：
如果所有元素后面都没有比他大的数字，那么这个数组就是一个单调递减的数组。如果按顺序把这个数组压栈，则这个栈也就是一个单调递减的栈。
那么如果我们构造一个单调栈，假如，我是说假如，此时有一个元素插进来，破坏了这个单调性，那么我们是不是可以认为，就找到了第一个比相应元素大的元素呢？
考虑一个测试例：
[9, 3, 5, 8, 2, 6]
实际上他还隐含了信息：位置。
我们可以写成这样：
[
<0, 9>,
<1, 3>,
<2, 5>,
<3, 8>,
<4, 2>,
<5, 6>
]
然后我们可以构造一个单调递减的栈，不同的是，我们在比较的时候使用值，但是在栈中存储的却是下标，原因也很简单，因为结果要的是距离，所以我们存下标嘛。
ok，那我们开始压栈了~
压9，此时栈中元素为[0]，并且结果的数组是[-1, -1, -1, -1, -1, -1]
压3，此时判断9大于3，于是正常压栈：[0, 1]
压5，此时发现3小于5，单调栈的结构要被破坏了，也就是说这个时候我们发现了比3大的第一个元素，于是出栈，并且可以更新3对应的距离了，结果数组变成了[-1, 1, -1, -1, -1, -1]
以此类推：当需要出栈的时候，就是更新结果之时，反之若一个下标值一直没有机会出栈，那么就说明从来没有数比他要大。
那么写成代码大概可以是这样的：
vector<int> findLarger(vector<int>& input) {
stack<int> tmp;
size_t len = input.size();
vector<int> output(len, -1);
for(int i = 0; i < len; i++) {
while(!tmp.empty() && input[i] < input[tmp.top()]) {
output[tmp.top()] = i - tmp.top();
tmp.pop();
}
tmp.push(input[i]);
}
return output;
}
看起来很简洁是不？而且复杂度也只是O（n）。每个元素最多进行一次入栈一次出栈。
OK，说完了单调栈的某些应用，我们可以来看看Leetcode的84题了。
这个题目我们只需要分析清楚一件事就够了：我们肯定是以某个矩形的顶为高来计算最大值的，所以我们只要想办法计算出以每个矩形为顶矩形的面积并迭代即可。这时候我们可以考虑维护一个递增的单调栈，当需要出栈的时候，说明以该矩形为顶的矩形的最大面积已经计算完毕了。（想想一下，如果右边元素比左边低了，那么左边那个顶为高度的矩形肯定已经无法向右边延展了）这个时候可以计算一下矩形的值，并且更新一下max了。
写成代码大概是这样的：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.insert(heights.begin(), 0);
heights.push_back(0);
stack<int> tmp;
int result = 0, sz = heights.size();
tmp.push(0);
for(int i = 1; i < sz; i++) {
while(heights[tmp.top()] > heights[i]) {
int h = heights[tmp.top()];
tmp.pop();
result = max(result, (i - tmp.top() - 1) * h);
}
tmp.push(i);
}
heights.erase(heights.begin());
heights.pop_back();
return result;
}
};
这样就够了。
这里用到讨论区某个大佬的一个trick，向头尾各插一个0进去，可以保证栈内有元素而省去一个判断栈是否为空的步骤。
总的来说，单调栈看起来简单，其实应用场景很灵活，有时候都很难想到要去使用单调栈来解决问题，这个还是因为菜……需要多练习ORZ。总的来说，求取某个一二维数组的，满足某种规则的极值，而这个极值还和相对位置强相关的时候，可以考虑使用单调栈解决。
