#

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

# 单调栈

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

# 练习题

# LC42 - 接雨水 (opens new window)

# LC84 - 柱状图中最大的矩形 (opens new window)

# CF1402A - Fancy Fence (opens new window)