今天做leetcode时，发现两道题均用到了单调递增栈，遂进行学习。
什么是单调递增栈？
简单来说，单调递增栈就是一个保持栈内元素为单调递增的栈。
单调递增栈的典型范式为
for(int i = 0; i < A.size(); i++){
while(! in_stk.empty() && in_stk.top() > A[i]){
in_stk.pop();
}
in_stk.push(A[i]);
}
单调递增栈的作用是什么？
1.以O(n)的计算复杂度找到vector中每一个元素的前下界(previous less element)
一个元素的前下界是指对这个元素“左边”的值，从这些值中找到一个greatest lower bound(也就是infimum)。
- 比如对于[ 3,7,8,4]这样一个数组来说。7的前下界是3；8的前下界是7；4的前下界是3；而3则没有前下界。
为了简单，我们使用PLE(Previous Less Element)来表示前下界。
- C++源代码
在考虑这个问题时，我们记录的是元素的索引而不是值。
// PLE[i] = j means A[j] is the previous less element of A[i]
// PLE[i] = -1 means there is no previous less element of A[i]
vector<int> PLE(A.size(), -1);
for(int i = 0; i < A.size(); ++i){
while(!in_stk.empty() && A[in_stk.top()] > A[i]){
in_stk.pop();
}
PLE[i] = in_stk.empty()? -1 : in_stk.top();
in_stk.push(i);
}
2.以O(n)的计算复杂度找到vector中每一个元素的后下界(next less element)
相似的，一个元素的后下界是一个元素右边的值中找到一个infimum.
- 比如对于[ 3,7,8,4]这样一个数组来说。7的后下界是4；8的后下界是4；而3和4均没有前下界。
同样为了简便，我们称后下界为NLE(Next Less Element)
- C++源代码
// NLE[i] = j means A[j] is the next less element of A[i]
// NLE[i] = -1 means there is no next less element of A[i]
vector<int> PLE(A.size(), -1);
for(int i = 0; i < A.size(); ++i){
while(!in_stk.empty() && A[in_stk.top()] > A[i]){
auto x = in_stk.top();
in_stk.pop();
NLE[x] = i;
}
in_stk.push(i);
}
给出相关题目的链接
参考文献
stack solution with very detailed explanation step by step
