单调栈

单调栈

栈内元素单调递增，操作 $O(1)$ 实现。 例：

直方图内最大矩形

$maxRect(r)=H[r]\cdot (t(r)-s(r))$ 通过一次遍历能确定 $s(r)$：单调栈 维护一个栈，栈内元素单调递增。从头到尾遍历数列，有两种情况：

• 新元素大于等于栈顶元素，$s(r)$ 等于自身的秩，直接入栈
• 新元素小于栈顶元素，重复将栈顶元素出栈直至栈顶元素小于等于当前元素。此时 $s(r)$ 等于栈顶元素的秩加一 同理，再进行一次反向扫描可以求出 $t(r)$。每个元素经历一次进栈一次出栈，总时间复杂度为 $O(n)$。

能否只通过一次扫描在线地得出答案？ 可以。可以发现，遍历数列时，若当前元素小于栈顶元素，对于栈顶元素，$s(r)$ 等于栈内次顶元素的秩，$t(r)$ 等于当前元素的秩。

Link to original