单调栈

一句话理解

单调栈：栈里元素单调，用来找左右第一个更大/更小。

为什么要学

O(n) 处理每个位置的近邻极值。

讲解

从左扫，弹出不满足单调的，栈顶就是答案。每个元素最多进一次出一次。

例子

找左边第一个比它小的：维护递增栈。

常见错误

• 弹出时没记录答案。
• 相等元素是否弹出看题目（严格小于）。