单调队列 & 单调栈

October 7, 2024

数据结构篇

省流

单调队列：获得区间(滑动窗口)的最值

单调栈：获得某元素周围第一个大于或者小于它的元素

实际运用多为以上两种情况，但仍需活学活用，不能被上面的两种情况限制。

之前在力扣评论区刷到过如下比喻：

公司的所有员工按年龄排列成一个单调的队列。

公司将不断招入年轻员工。如果年轻员工比某些老员工能力强，那就毫不犹豫踢掉这些老员工(补药啊)。

同时，踢掉大于35岁的老员工，无论能力多强都踢掉。

这个比喻就把单调队列的出入队概括完了，很好理解。

单调队列怎么做到通过维护一个队列，队头刚好是所求区间上的最大值呢（最小值同理，以下例子为最大值）？

首先，很容易明白的一点，就是这个区间的最大值一定能留在队头。

我们担心的是，这个最大值一旦离开区间了，谁来当二把手呢？

我们想到可以搞个二把手候选人队列，有可能当二把手的元素都进来，从大到小排着，老大挂了就上老二。

那为什么要让能力强的新人把比他弱的老东西踢掉呢？因为新人能活最久，并且当二把手的优先级也高于老东西，那这些老东西一定是不可能当二把手的，不符合我们队列的要求，所以直接踢掉。

单调栈也完全可以通过上面的比喻来理解。但是不能踢35岁老员工了，~~单调栈是一个尊重老人的公司~~。

获得某元素周围第一个大于或者小于它的元素是什么意思呢？

当一个新人比一堆老员工强的时候，这些老员工全会被踢。所以，这个新人就是第一个比这些老员工强的人。换句话说，新入栈的元素是第一个比因为这个元素而退栈的元素大的元素。这句话很绕，慢点读别噎着了。

但这样我们只能做一个方向。所以得维护两个单调栈，就能得到每个元素“周围”的满足要求的元素了。