单调栈是什么
从名字上来看单调栈与单调队列十分的相似,同样的它们的具体内容也十分的相似。单调栈本质上是一个栈,这个栈中的元素是严格有序(即不存在相等元素)的,所以栈顶元素总是比栈里的元素大或小,用公式表达如下:
∀i∈[0,n){Stacki+1>Stacki,Stacki+1<Stacki,NGENLE
其中 NGE 指的是 Next Greater Element,即下一个比它大的元素,而 NLE 指的是 Next lower Element,即下一个比它小的元素。
单调栈用来干什么
解决 NGE、NLE 问题。
如何维护单调栈
以 NGE 问题为例。
我们需要获取序列中第i 个元素之后第一个大于ai的元素的下标,联想到单调栈的性质即使用单调栈解决此题。
我们维护一个栈stack
,遍历序列a 时进行如下操作:
- 检查
stack
是否为空,如果是则将i
入栈并进行下一次判断(continue
)。 - 不断检查
stack
的栈顶元素(下标)在a 中的取值并且如果a[i]>a[stack.top],就将stack.top
的答案设置为i
,因为i
为下一个比它大的元素。
不难发现,经过以上的维护,栈stack
内的元素始终是有序的,所以答案的正确性也就得到了保证。
code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| #include <iostream> #include <stack>
using namespace std;
const uint32_t MAX_N = 3e6 + 10;
uint32_t n; uint32_t a[MAX_N], ans[MAX_N]; stack<uint32_t> stk;
int main() { ios::sync_with_stdio(false);
cin >> n; for (uint32_t i = 1; i <= n; ++i) { cin >> a[i]; }
for (uint32_t i = 1; i <= n; ++i) { while (stk.size() && a[stk.top()] < a[i]) { ans[stk.top()] = i; stk.pop(); } stk.push(i); }
for (uint32_t i = 1; i <= n; ++i) { cout << ans[i] << ' '; } cout << endl;
return 0; }
|