单调栈
单调栈是具有单调性的栈（如递增、非递减），能提高解决特定问题的效率，例如找到某个元素左边或右边第一个比它大或小的元素。
应用（例题）
给出项数为 n 的整数数列 a1…n。定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai 的元素的下标。若不存在，则 f(i)=0。试求出 f(1…n)。
解法
数据范围大，遍历不可行。需使用单调非递增栈。留在栈内的数是目前为止未找到大于自身元素的数。当新数进栈时，若栈顶元素小于它，说明找到了大于栈顶的数，弹出栈顶，重复直至条件不满足，最后压入当前数。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,f[4000050];
struct node{ ll val,pos; }a[4000050];
stack<node>sk;
void solve(node x){
while(!sk.empty()){
node y=sk.top();
if(y.val<x.val){
f[y.pos]=x.pos;
sk.pop();
}else break;
}
sk.push(x);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].val;
a[i].pos=i;
solve(a[i]);
}
for(int i=1;i<=n;i++){
cout<<f[i]<<' ';
}
return 0;
}
单调队列
单调队列是具有单调性的队列，同样能提高效率。
