有一些关于数组中数值比较类型的题目，通常O(n2)的解法是可以得到正确的解，但是，当数组范围较大时，需要尽可能采取O(n)的解法。单调栈通常是一个很好的算法。
单调栈的算法，在leetcode中有大量的题目涉及，该算法确实是一个非常高效是算法。
原理如下：
1）单调栈的栈中存储的元素为数组索引，通常用以解决无序数组按一定条件进行遍历的相关问题。
2）以单调递减栈为例，stack[i]存储的是数组索引，单调栈的种类有两个：
在一个数组上从下标0开始从左到右遍历，若元素a小于栈顶元素则压入。对于栈中元素s[i]而言，s[i]为区间[0, s[i + 1])的最小值的索引；
在一个数组上从下标0开始从左到右遍历，若元素e大于等于栈顶元素则将栈顶元素弹出直到e小于栈顶元素再入栈，s[i]为区间(s[i - 1], pos]的极大值的索引，pos为当前遍历位置。
下面这个帖子，讲的比较好，供参考。
https://blog.csdn.net/liujian20150808/article/details/50752861
leetcode相关题目
496. 下一个更大元素 I
该题应该是单调递增栈的模板代码。
通过单调递增栈，为num2数组中的每个元素找到它的下一个最大元素。由于num1是num2的子数组，所以选择map存储num1的处理结果。
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> s;
unordered_map<int, int> m;
for (int n : nums2) {
while (s.size() && s.top() < n) { //一直在走下坡路，突然遇到一个上坡，看看是否可以逆袭
m[s.top()] = n;
s.pop();
}
s.push(n);
}
vector<int> ans;
for (int n : nums1) ans.push_back(m.count(n) ? m[n] : -1);
return ans;
}
};
题解
代码
class Solution {
public:
int maxWidthRamp(vector<int>& A) {
stack<int> s;
int ans = 0;
s.push(0);
for (int i = 1; i < A.size(); i++) {
if(A[i] < A[s.top()])
s.push(i);
}
for (int i = A.size() - 1; i >= 0; i--) {
while (!s.empty() && A[i] >= A[s.top()]) {
ans = max(ans, i - s.top());
s.pop();
}
if ( i < ans) break;
}
return ans;
}
};
题解
这道题的关键在于求解两个柱子之间的空间面积。
说下想法：
1）两个柱子之间的距离 高度如何求解
2）如何排除类似 0 0 0 0 1这种不可接雨水的情况
基于单调栈的算法我一开始是想到了的，并且计算出了距离，但是一直没想好怎么求解高度，为了加深记忆，我画个图来分析高度的求解方法。
从分析可以看出，单调栈可能涉及到三个索引位置
1）数组中当前正在比较的索引
2）栈顶元素
3）栈中做回溯，通过回溯找到一个合适的位置
代码
class Solution {
public:
int trap(vector<int>& height) {
stack<int> s;
int res = 0;
int high = 1;
for (int i = 0; i < height.size(); i++) {
while (!s.empty() && height[s.top()] <= height[i]) {
int top = s.top();s.pop();
if (s.empty()) break;
int length = i - s.top() - 1;
int high = min(height[i], height[s.top()]) - height[top];
res += length * high;
}
s.push(i);
}
return res;
}
};
题解
代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
if (heights.empty()) return 0;
stack<int> sk;
int area = 0;
heights.push_back(0);
for (int i = 0; i < heights.size(); i++) {
while (!sk.empty() && heights[i] < heights[sk.top()]) {
int top = sk.top();
sk.pop();
int w = sk.empty() ? i : i - sk.top() - 1;
area = max(area, w * heights[top]);
}
sk.push(i);
}
return area;
}
};
单调栈算法总结
1）递增栈，还是递减栈的选择，可以考虑用排除思想
2）算法融入，通常单调栈可以解决的问题中，用贪心算法比较多。
3）三个关键点，1、当前索引 2、栈顶出栈元素 3、回溯元素
4）元素是否需要全部出栈，如果需要则需要构造条件完成元素出栈。
5）面积相关问题中，关于高度和宽度的求解通常容易犯糊涂，这部分还是要多想想。
好啦，经过上面几道题的训练，关于栈以及单调栈的应用，应该算比较有数了。
