单调栈

拥有栈的先进后出（FIFO）的特性，同时栈内元素具有单调性。若从栈底到栈顶单调递增，则为单调递增栈，若从栈底到栈顶单调递减，则为单调递减栈。

性质

单调递增栈中，栈内每一个元素，其前一个元素（往栈底的方向看）是其左边的第一个比其小的元素；当遇到一个新元素使其被弹出时，这个新元素是其右边的第一个比其小的元素。

单调递减栈中，栈内每一个元素，其前一个元素（往栈底的方向看）是其左边的第一个比其大的元素；当遇到一个新元素使其被弹出时，这个新元素是其右边的第一个比其大的元素。

一般可以应用于需要往其左右两边寻找最近的比其大或小的元素，可以将暴力的寻找方法的时间由 $O(n^2)$ 缩减为 $O(n)$。

应用

• 42. 接雨水
• 84. 柱状图中的最大矩形
• 85. 最大矩形
• 503. 下一个更大元素 II

扩展

根据单调栈的性质，一个栈内元素可以找到其左右两边第一个比其大或小的元素，若要找到第二个比其大或小的元素，则可以使用两个单调栈，而为了中间数据的中转，只要再加一个临时栈作为辅助。若要找到第 k 个，则同理扩展，但 k 过于大时，编写起来可能有些麻烦，且此时时间 $O(kn)$ 可能与 $O(n^2)$ 相差无几，可以考虑重新使用暴力的寻找方法。