认识单调队列【蓝桥杯算法】2026/3/27

首先什么是单调队列：
单调队列是一个双端队列（两头都可进可出），存储的是单调递增或递减的元素。

解决什么问题：
解决滑动窗口最大值最小值问题，以及优化动态规划。

示例（求长度为L的窗口每滑动一次的窗口内的最大值）：
原数组：[1,10,5,4,9,15,12]
维护一个双端队列满足：
如果队列为空，添加一个元素；
1.接下来如果当前元素比队尾元素小，则加入队尾（为什么小的元素还要加入队尾呢？是因为窗口在滑动可能会失去队头的那个大的元素），如果队列元素大于窗口值则从队头弹出元素。
2.如果当前元素比队尾元素大，则将队尾元素弹出，直到队尾元素比当前元素大，或者队列为空
3.如果当前元素的下标减去队头下标大于窗口值，就要弹出队头（因为我们要维护问题中窗口大小固定这个性质）
这两个判断完毕后，队头元素就是最大值。

相反的，求窗口最小值就是小变成大。
以下是推演过程：
原数组[1,10,5,4,9,15,12]
队列：
【1】
【10】：解释：10比1大，队头弹出1，队尾弹出10；
【10，5】：解释：5比10小，队尾加入5；这时遍历到窗口大小为3，最大值为队头10.
【10，5，4】最大值为10
【9】：队头元素的位置和当前元素的位置大于3，超过窗口值，需弹出超过的10，9比4和5大，队尾弹出4、5，加入9；
【15，12】以下步骤省略