单调栈

title: 单调栈
date: 2022-11-17 20:33:16
tags: 算法

本文章遵守知识共享协议 CC-BY-NC-SA ，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

单调栈是一种可以在线性时间中计算出一个序列中 大于/小于 任意一个左/右元素的值。

前置知识

• 栈

讲解

单调栈，顾名思义，就是内部元素保持单调的栈。

对于维护，我们只需要在加入时先判断

for(int i=1;i<=n;i++){
    scanf("%d",&tmp);
    while(!st.empty() && tmp > st.top()){
        flg[id.top()] = i; // 标记
        st.pop(); // 弹出
        id.pop(); // 弹出
    }
    id.push(i);
    st.push(tmp);
}
flg[id.top()] = 0;

例题

P5788-【模板】单调栈

模板题目，直接做。