单调栈
单调栈，顾名思义就是具有单调性的栈（例如递增，非递减等）。它能提高解决一些问题（如找到某个元素左边或右边第一个比它大或小的元素）的效率。
应用（例题）
解释起来非常简单，还是看例题：
给出项数为 n 的整数数列 a1…n。 定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai 的元素的下标，即 f(i)=mini<j≤n,aj>ai{ j}。若不存在，则 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; }
