最近刷了不少单调栈,总算搞懂了
基本性质
- 入栈顺序为下标顺序。
- 出栈序列分批次为单调增/单调减。
- 每个元素应当入栈一次出栈一次,复杂度为O(N)
利用好这3点性质,是发挥单调栈作用的关键:
对于性质1,我们可以认为:当你使用了单调栈,那么你所解决的问题一定与数组下标顺序(或者排序后的数组下标顺序)有关系。相当于帮你固定了题目中的一组偏序。对于性质2,我们认为:想要使用单调栈,那么答案或者中间结果必然具有某种单调性。对于性质3,当我们需要O(N)算法时,可以考虑单调栈。
说的过于抽象了,看题。
READ MORE →