有一些關(guān)于數(shù)組中數(shù)值比較類型的題目，通常O(n2)的解法是可以得到正確的解，但是，當(dāng)數(shù)組范圍較大時(shí)，需要盡可能采取O(n)的解法。單調(diào)棧通常是一個(gè)很好的算法。
單調(diào)棧的算法，在leetcode中有大量的題目涉及，該算法確實(shí)是一個(gè)非常高效是算法。
原理如下：
1）單調(diào)棧的棧中存儲的元素為數(shù)組索引，通常用以解決無序數(shù)組按一定條件進(jìn)行遍歷的相關(guān)問題。
2）以單調(diào)遞減棧為例，stack[i]存儲的是數(shù)組索引，單調(diào)棧的種類有兩個(gè)：
在一個(gè)數(shù)組上從下標(biāo)0開始從左到右遍歷，若元素a小于棧頂元素則壓入。對于棧中元素s[i]而言，s[i]為區(qū)間[0, s[i + 1])的最小值的索引；
在一個(gè)數(shù)組上從下標(biāo)0開始從左到右遍歷，若元素e大于等于棧頂元素則將棧頂元素彈出直到e小于棧頂元素再入棧，s[i]為區(qū)間(s[i - 1], pos]的極大值的索引，pos為當(dāng)前遍歷位置。
下面這個(gè)帖子，講的比較好，供參考。
https://blog.csdn.net/liujian20150808/article/details/50752861
leetcode相關(guān)題目
496. 下一個(gè)更大元素 I
該題應(yīng)該是單調(diào)遞增棧的模板代碼。
通過單調(diào)遞增棧，為num2數(shù)組中的每個(gè)元素找到它的下一個(gè)最大元素。由于num1是num2的子數(shù)組，所以選擇map存儲num1的處理結(jié)果。
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) { //一直在走下坡路，突然遇到一個(gè)上坡，看看是否可以逆襲
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;
}
};
題解
這道題的關(guān)鍵在于求解兩個(gè)柱子之間的空間面積。
說下想法：
1）兩個(gè)柱子之間的距離 高度如何求解
2）如何排除類似 0 0 0 0 1這種不可接雨水的情況
基于單調(diào)棧的算法我一開始是想到了的，并且計(jì)算出了距離，但是一直沒想好怎么求解高度，為了加深記憶，我畫個(gè)圖來分析高度的求解方法。
從分析可以看出，單調(diào)?？赡苌婕暗饺齻€(gè)索引位置
1）數(shù)組中當(dāng)前正在比較的索引
2）棧頂元素
3）棧中做回溯，通過回溯找到一個(gè)合適的位置
代碼
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;
}
};
單調(diào)棧算法總結(jié)
1）遞增棧，還是遞減棧的選擇，可以考慮用排除思想
2）算法融入，通常單調(diào)?？梢越鉀Q的問題中，用貪心算法比較多。
3）三個(gè)關(guān)鍵點(diǎn)，1、當(dāng)前索引 2、棧頂出棧元素 3、回溯元素
4）元素是否需要全部出棧，如果需要則需要構(gòu)造條件完成元素出棧。
5）面積相關(guān)問題中，關(guān)于高度和寬度的求解通常容易犯糊涂，這部分還是要多想想。
好啦，經(jīng)過上面幾道題的訓(xùn)練，關(guān)于棧以及單調(diào)棧的應(yīng)用，應(yīng)該算比較有數(shù)了。
