滑动窗口最大值

GitHub跳转原题关系图返回列表

单调递减队列保存候选下标，过期从队首删，较小候选从队尾删，O(n)。

OJ: leetcodecn

题目 ID: sliding-window-maximum

难度:提高+/省选-

标签:队列单调队列滑动窗口数组cpppython

日期: 2026-07-28 22:05

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定数组和滑动窗口大小 k，返回每个窗口的最大值。

思路

暴力 O(nk) 每个窗口扫一遍最大值。优化：用单调递减队列保存窗口内可能成为最大值的元素下标。

  • 队首始终是当前窗口的最大值。
  • 新元素入队时，从队尾弹出所有比它小的元素（它们再也不可能成为最大值）。
  • 队首超出窗口范围时弹出。

每个元素至多入队出队一次，均摊 O(n)。

代码

cpp
/**
 * Author by Rainboy
 */
// main.cpp：单调递减队列，O(n)。
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k) {
        deque<int> q;
        vector<int> ans;
        for (int i = 0; i < (int)nums.size(); i++) {
            while (!q.empty() && q.front() <= i - k)
                q.pop_front();
            while (!q.empty() && nums[q.back()] <= nums[i])
                q.pop_back();
            q.push_back(i);
            if (i >= k - 1)
                ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    auto v = Solution().maxSlidingWindow(a, k);
    for (int x : v)
        cout << x << ' ';
    return 0;
}
python
#!/usr/bin/env python3
from typing import List
from collections import deque


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()
        ans = []
        for i, x in enumerate(nums):
            while q and q[0] <= i - k:
                q.popleft()
            while q and nums[q[-1]] <= x:
                q.pop()
            q.append(i)
            if i >= k - 1:
                ans.append(nums[q[0]])
        return ans


def main() -> None:
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    print(*Solution().maxSlidingWindow(nums, k))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(n)，每个元素入队出队各一次。
  • 空间复杂度：O(k)，队列最多存 k 个元素。

总结

单调队列适用于"滑动窗口最值"问题，"被更大值淘汰"的永久性是保证 O(n) 的关键。该模型与单调栈对称：栈处理的是固定端点向一侧扩展，队列处理的是连续滑动窗口。