单调栈

约 140 个字 12 行代码 预计阅读时间 1 分钟

$O(n)$ 解决NGE问题（Next Greater Element），即序列中每个元素的下一个比它大的元素

维护一个栈stack，表示待确定NGE的元素

遍历序列，当新元素比栈顶大，说明新元素就是栈顶的NGE，弹出栈顶继续比较，直到新元素不比栈顶大，新元素入栈。

根据上面操作过程，显然栈内元素单调递减

组的题里有专门考单调栈的，但是区域赛真题大多是用单调栈优化DP的

int a[N],nge[N];
stack<int> sta;
a[n]=INF;
for(int i=0;i<=n;++i)
{
    while(!sta.empty() && a[i]>a[sta.top()])
    {
        nge[sta.top()]=i;
        sta.pop();
    }
    sta.push(i);
}