单调栈

顾名思义，单调栈即满足单调性的栈结构。与单调队列相比，其只在一端进行进出。

相对于普通的栈结构，在处理单调栈时需要额外地关心在进行插入操作时需要将违背单调性的斩顶元素先弹出。代码：

1
2
3

while (!sta.empty() && sta.top() < x)
    sta.pop()
sta.push(x)

应用

离线解决 RMQ(Range Maximum/Minimum Query) 问题，即求解一个区间中的最大、最小值问题。