单调栈

以739. 每日温度为引入

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

很容易想到$O(N^2)$的暴力解法 —— 对于当前的时刻,遍历之后的所有时刻找到第一个更高温度出现的下标即可.

但是非常坏,在每一次遍历的时候,读取到的温度信息会在此次循环结束之后就被”弃用“,导致时间复杂度大涨.

那么时候单调栈来对温度进行缓存 ——

• 保证栈内的温度信息是单调递减的
• 循环 —— 当前温度大于栈顶的元素时
  • 弹出栈顶元素,存储天数
• 插入当前天气信息进入单调栈维护

这样所有元素只需要“入栈、出栈”即可,时间复杂度降到了$O(N)$

单调栈

比正常的栈多一层”单调“ —— 保证栈内元素是单调递增或递减的.

运用: 主要用于在$O(N)$的时间复杂度下解决,NGE/NSE (Next Greater/Smaller Element) 问题

理解: 缓存“历史遗留问题”,在遇到可以解决的机遇之时一股脑全部解决掉.