单调队列模板

一句话说明

单调队列不会保存窗口里所有元素，它只保留“未来还有资格当答案”的那些下标。

先抓住三个动作

对于滑动窗口最大值：

1. 删掉队头过期下标
2. 删掉队尾比新元素更差的下标
3. 把新下标入队

做完这三步后：

• 队头就是当前窗口最大值下标

为什么一定要存下标

因为你不仅要比较大小，还要判断：

这个元素是不是已经滑出窗口了

只存值的话，无法判断谁过期。

Go 模板：固定窗口最大值

func MaxSlidingWindow(nums []int, k int) []int {
    if k <= 0 || k > len(nums) {
        return nil
    }
 
    deque := []int{}
    result := make([]int, 0, len(nums)-k+1)
 
    for right, value := range nums {
        left := right - k + 1
 
        for len(deque) > 0 && deque[0] < left {
            deque = deque[1:]
        }
 
        for len(deque) > 0 && nums[deque[len(deque)-1]] <= value {
            deque = deque[:len(deque)-1]
        }
 
        deque = append(deque, right)
 
        if left >= 0 {
            result = append(result, nums[deque[0]])
        }
    }
 
    return result
}

模板里的不变量

求最大值时：

• 队列里的下标严格递增
• 对应值从队头到队尾严格单调递减
• 队头始终属于当前窗口

所以队头就是答案。

求最小值怎么改

只改一处核心判断：

把维护递减队列
改成维护递增队列

也就是把：

nums[deque[last]] <= value

改成：

nums[deque[last]] >= value

为什么复杂度是 O(n)

因为每个下标：

• 最多入队一次
• 最多从队头或队尾出去一次

所以总操作数是线性的。

常见题型

• 滑动窗口最大值 / 最小值
• 前缀约束下的最优值
• 某些 DP 优化

易错点

单调队列模板最容易错的地方

• 必须存下标，不要只存值。
• 先删过期，再维护单调性，再入队。
• 最大值维护递减队列，最小值维护递增队列。
• 相等元素通常弹掉旧的，保留新的，更不容易过期失控。

相关主题

• 单调栈与单调队列
• 队列

---

返回：算法模板