单调栈
2019年6月23日 星期天, 发表于 深圳
如果你对本文有任何的建议或者疑问, 可以在 这里给我提 Issues, 谢谢! :)
单调栈是一种特殊的数据结构，需要保持栈单调，具体可以参考oi-wiki.org
2.2 数据结构
参考 https://blog.csdn.net/liujian20150808/article/details/50752861
- 单调栈里的元素具有单调性
- 元素加入栈前，会在栈顶端把破坏栈单调性的元素都删除
- 使用单调栈可以找到元素向左遍历第一个比他小的元素，也可以找到元素向左遍历第一个比他大的元素。
while !sta.empty() && sta.top()<x
sta.pop()
sta.push(x)
2.3 用途
2.3.1 问题一
建议阅读原文：https://zhuanlan.zhihu.com/p/26465701
Q: 给一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1）。
A: 其中O(N^2)的解法不赘述，看一下如何使用单调栈来实现：
vector<int> nextExceed(vector<int> &input) {
vector<int> result (input.size(), -1);
stack<int> monoStack;
for(int i = 0; i < input.size(); ++i) {
while(!monoStack.empty() && input[monoStack.top()] < input[i]) {
result[monoStack.top()] = i - monoStack.top();
monoStack.pop();
}
monoStack.push(i);
}
return result;
}
2.3.2 leetcode (84)
题目链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
首先回想一下单调栈的功能，找到比他大/小的元素;
class Solution {
public:
int largestRectangleArea(vector<int>& heights) //[2,1,5,6,2,3]
{
heights.push_back(0);
stack<int> stackIndex;
int maxArea = 0;
for (size_t i = 0; i < heights.size(); i++)
{
//弹出的元素，说明以他的高度为高的矩形无法向右再扩充面积了
while (!stackIndex.empty() && heights[stackIndex.top()] >= heights[i])
{
int height = heights[stackIndex.top()]; //当前矩形的高度
stackIndex.pop();
int startPos = (stackIndex.empty()?-1:stackIndex.top() ) + 1; //startPos是第一个位置比heiigth高的位置
int width = i - startPos;
int area = height * width;
if( area > maxArea )
{
maxArea = area;
}
}
stackIndex.push(i); //stackIndex内的每一元素单调增加
}
return maxArea;
}
};
看了答案很久，才看明白。
使用递增的单调栈，如果遇到一个比它小的元素，此时弹出栈中的元素，栈中的元素所有的高度都应该比当前元素要高；
那么以栈中的元素为高的矩形，它的左右边界在哪里呢？
- 右边界应该是当前处理的位置的前一个位置，为什么呢？因为当前栈的位置可以一直衍生到当前处理处理的位置（递增）；
- 左边界应该是当前栈top-1的前一个位置（因为所有的top-1之后的元素都是大于当前栈位置的，不然已经被弹出去了）
3. 总结：
参考这里的建议： https://www.1point3acres.com/bbs/thread-204388-1-1.html
- 单调栈何时用： 为任意一个元素找左边和右边第一个比自己大/小的位置，用单调栈
- 用递增单调栈还是递减单调栈：递减栈会剔除波谷，留下波峰；递增栈剔除波峰，留下波谷