单调栈

发布时间 2023-04-03 23:04:33作者: 是谁不可理喻

第一次听说单调栈是在cf上看到的,当时看的糊里糊涂,正好算法进阶指南上有单调栈,赶紧看看

cf题:https://codeforces.com/contest/1795/problem/E

单调栈,顾名思义,栈内的元素单调排序,当题目满足某些性质时,单调栈的先进后出性质显得尤为重要,滑动窗口模拟优先队列便是这样。

书上的第一道例题就让我大开眼界

 

 如何在保留原有数据进出顺序的同时,做到O(1)的获取最小值

很简单,单开一个栈b,保存a中以栈底为开头的每段数据的最小值

每当push进一个新的数,只要和b栈顶的数比较,如果小于等于它,就push,大于的话,就不管

而当要pop掉a的栈顶时,只需要比较a的栈顶和b的栈顶是否一样,如果一样,则b也pop

有一个细节:push时,比对关系有等于,为的是防止出现一个极小的数字重复出现