滑动窗口最大值 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

比喻

这是一个降本增笑的故事：

如果新员工比老员工强（或者一样强），把老员工裁掉。（元素进入窗口）
如果老员工 35 岁了，也裁掉。（元素离开窗口）

裁员后，资历最老（最左边）的人就是最强的员工了。

视频讲解

请看单调队列【基础算法精讲 27】，欢迎点赞关注~

单调队列套路

右边入（元素进入队尾，同时维护队列单调性）
左边出（元素离开队首）
记录/维护答案（根据队首）

答疑

问：为什么代码中的「队首离开窗口」写的是 $if$ 而不是 $while$ ？

答：注意窗口在一步一步地向右滑动（像只蜗牛），所以元素也是一个一个地离开窗口，不会出现同一轮循环中有多个元素离开窗口的情况。

Python 解法1C++ 解法1

python

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = [0] * (len(nums) - k + 1)  # 窗口个数
        q = deque()  # 双端队列

        for i, x in enumerate(nums):
            # 1. 右边入
            while q and nums[q[-1]] <= x:
                q.pop()  # 维护 q 的单调性
            q.append(i)  # 注意保存的是下标，这样下面可以判断队首是否离开窗口

            # 2. 左边出
            left = i - k + 1  # 窗口左端点
            if q[0] < left:  # 队首离开窗口
                q.popleft()

            # 3. 在窗口左端点处记录答案
            if left >= 0:
                # 由于队首到队尾单调递减，所以窗口最大值就在队首
                ans[left] = nums[q[0]]

        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans(n - k + 1); // 窗口个数
        deque<int> q; // 双端队列

        for (int i = 0; i < n; i++) {
            // 1. 右边入
            while (!q.empty() && nums[q.back()] <= nums[i]) {
                q.pop_back(); // 维护 q 的单调性
            }
            q.push_back(i); // 注意保存的是下标，这样下面可以判断队首是否离开窗口

            // 2. 左边出
            int left = i - k + 1; // 窗口左端点
            if (q.front() < left) { // 队首离开窗口
                q.pop_front();
            }

            // 3. 在窗口左端点处记录答案
            if (left >= 0) {
                // 由于队首到队尾单调递减，所以窗口最大值就在队首
                ans[left] = nums[q.front()];
            }
        }

        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为 $nums$ 的长度。虽然写了个二重循环，但队列入队 $n$ 个元素，所以 q.pop() 出队至多执行 $n$ 次，所以二重循环的循环次数只有 $O (n)$ 。
空间复杂度： $O (min (k, U))$ ，其中 $U$ 是 $nums$ 中的不同元素个数（本题至多为 $20001$ ）。双端队列至多有 $k$ 个元素，同时又没有重复元素，所以也至多有 $U$ 个元素，所以空间复杂度为 $O (min (k, U))$ 。返回值的空间不计入。

思考题（2026.6.15 添加）

对于 $k = 1, 2, \dots, n$ ，计算本题的答案。

具体地，返回一个长为 $n$ 的数组 $answers$ ，其中 $answers [i]$ 表示 $k = i + 1$ 时本题的答案。

要求：时间复杂度 $O (n)$ 。

欢迎在评论区分享你的思路/代码。

专题训练

见下面数据结构题单的「§4.4 单调队列」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

比喻 ​

视频讲解 ​

单调队列套路 ​

答疑 ​

复杂度分析 ​

思考题（2026.6.15 添加） ​

专题训练 ​

分类题单 ​

比喻