栈

栈（Stack）是一种具有后进先出特性的线性数据结构。

单调栈

单调栈（Monotonic Stack）在数据结构层面就是最普通的栈，但我们需要在新元素入栈时维护一个栈的单调性，使栈中的元素始终保持升序或降序。在一类与区间有关的问题中，单调栈可以实现 $O(N)$ 的复杂度，因为每个元素至多入栈和出栈一次。