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