单调栈

单调栈(Monotonic Stack)是一种特殊的栈，它首先是一个栈，从栈顶添加和删除元素，其次栈中的所有元素单调递增或者单调递减

在一个队列Deque中，我们offer右边，poll左边，这样左边就是队首，右边是队尾

如果这个Deque作为栈，我们push和pop左边，并且把左边作为栈顶

单调性的判断是从栈顶到栈底（Deque中从左往右看）

  • 单增栈：栈顶到栈底的元素是单调递增的，即栈顶的元素最小

  • 单减栈：栈顶到栈底的元素是单调递减的，即栈顶的元素最大

  • 后上界：对于数组中的某个元素 a[i]，它的后上界是指在它之后的第一个比它大的元素

  • 后下界：对于数组中的某个元素 a[i]，它的后下界是指在它之后的第一个比它小的元素

单调栈在算法中的应用在于它能够在一次扫描(从左到右)即O(n)的复杂度之内找到数组中每一个元素的后上界(单增栈)或者后下界(单减栈)

单调队列

从「维护单调性」的角度上来说，单调队列和单调栈是一样的。在单调栈的基础上，单调队列多了一些「栈底」的操作，这类似滑动窗口移动左指针 left 的过程。所以从某种程度上来说，单调队列 = 单调栈 + 滑动窗口。