[!info] related notes 滑动窗口最大值 单调栈

单调队列

单调队列维护一组按值单调排列的候选元素，常用于滑动窗口最值，也可用于具有区间转移范围的 DP。它与寻找最近更大/更小元素的 单调栈 有相似的淘汰逻辑，但还需要从队首删除过期候选。

窗口最大值的两个不变量

• 队列存下标，下标从队首到队尾递增，用来判断是否仍在窗口内。
• 对应值从队首到队尾递减或不增，队首就是当前最大值的候选。

每读到 nums[i]，先删除小于 i - k + 1 的过期下标，再从队尾删除被新元素支配的候选，最后把 i 入队。

新元素若不小于旧元素，且更晚离开窗口，旧元素就不再有成为最大值的必要。使用 <= 淘汰旧候选会保留最新的相等值；使用 < 保留相等值也能求出正确最大值，只是队列可能更长。若还要求最早最大值的下标，等值策略就会影响结果。

复杂度的前提

每个下标最多入队一次、出队一次，所以双端操作总数为 O(n)。要得到 O(n) 时间，还需双端操作为 O(1) 或摊销 O(1)；不能直接从操作次数推断任意底层容器的耗时。

JavaScript Array.shift() 不提供常数时间保证。可用真正的 deque、循环数组，或头指针避免每次从数组开头删除。单纯递增头指针会保留已过期前缀，逻辑队列虽至多 O(k)，底层数组仍可能占 O(n) 空间；需要复用或压缩存储才能严格控制到 O(k)。

具体题解与头指针实现见 滑动窗口最大值。