2020.02.23日常总结兼单调栈略讲

$\color{green}{单调栈}$单调栈

• 顾名思义，单调栈就是内部元素单调（递增、递减、不增、不减都叫单调）的栈。
• 常常用来完成找离一个数最近且大于、小于、大于等于、小于等于它的数。
• 效率极高，常常是 $O(N)$O(N) 的，而且它非常像一个不能删除的单调队列。
• 实现上，我们就用一个栈就可以实现了，只是要维护它内部元素的单调性即可。
• 何时需要维护？删除不需要，查询不需要，$\color{red}{只有加入元素需要}$只有加入元素需要。

$\color{green}{洛谷\text{P5788}\ \ \ 【模板】单调栈}$洛谷P5788   【模板】单调栈

$\color{blue}{【题意】：}$【题意】：

$\color{blue}{【思路】：}$【思路】： 单调栈的模板题。用一个内部元素严格递增的栈 $S$S 维护。当我们处理到一个元素 $a_i$ai​ 时，我们把 $S$S 的顶部 $\leq a_i$≤ai​ 的元素全部删除。$f(i)$f(i) 就是删除后 $S$S 的栈顶的元素的下标。注意必须从小到大枚举。

$\color{blue}{【代码】：}$【代码】：