LeetCode 239. 滑动窗口最大值

◎

本节目标

在固定长度窗口上维护单调递减下标队列，在线输出每个窗口的最大值。

这道题放在数组与矩阵综合中，因为它把固定长度窗口与单调队列组合起来：窗口控制范围，队列控制最大值候选。

查看原题

题意与约束

给定整数数组 nums 和窗口大小 k，从左到右滑动长度为 k 的窗口，返回每个窗口中的最大值。数组元素可为负数，重复最大值也必须正确保留。

若每个窗口都重新扫描 k 个元素，总时间为 O(nk)。需要一种能随窗口移动快速丢弃过期元素、又能直接读出最大值的状态。

单调队列为什么保存下标

双端队列保存候选元素的下标，并保证从队首到队尾对应的数值严格递减。队首因此始终是当前候选中的最大值。

处理右端下标时，先移除队首所有已经落在窗口左侧的下标；再从队尾移除值不大于当前值的下标，它们以后既更小又更早过期；最后加入当前下标。窗口长度达到 k 时，输出队首对应的值。

保存下标而不是值，才能准确判断元素是否已经离开窗口。

代码实现

两份源码使用删除不大于当前值的队尾候选，所以相同最大值只保留较新的下标；这不会影响当前最大值，并让旧下标更早离开队列。

C++

C++17

#include <deque>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> candidates;
        vector<int> answer;

        for (int right = 0; right < static_cast<int>(nums.size()); right++) {
            while (!candidates.empty() && candidates.front() <= right - k) {
                candidates.pop_front();
            }
            // 队列从前到后保持对应值严格递减。
            while (!candidates.empty() && nums[candidates.back()] <= nums[right]) {
                candidates.pop_back();
            }
            candidates.push_back(right);
            if (right >= k - 1) {
                answer.push_back(nums[candidates.front()]);
            }
        }
        return answer;
    }
};

Python

Python 3

from collections import deque


class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        candidates: deque[int] = deque()
        answer: list[int] = []

        for right, value in enumerate(nums):
            while candidates and candidates[0] <= right - k:
                candidates.popleft()
            # 队列从前到后保持对应值严格递减。
            while candidates and nums[candidates[-1]] <= value:
                candidates.pop()
            candidates.append(right)
            if right >= k - 1:
                answer.append(nums[candidates[0]])
        return answer

复杂度分析

• 时间复杂度：O(n)。每个下标至多入队一次、从两端各移出一次。
• 空间复杂度：O(k)。队列最多保存当前窗口内的候选下标。

易错点

• 队列保存值，导致无法识别已经过期的相同值。
• 先输出再清理窗口外下标，可能把过期最大值写入答案。
• 队尾只删除小于当前值的候选；虽然可行，但保留相等的旧下标更容易增加过期处理负担。

模式迁移

它建立在滑动窗口解题框架的固定长度窗口上。把频次或和替换为单调候选队列后，同一结构还能求窗口最小值，或处理需要维护某种单调边界的在线区间问题。