HJ176. 【模板】滑动窗口

题目描述

给定长度为 n 的整数数组和一个窗口大小 k，滑动窗口从左到右每次右移一位，输出每个窗口内元素的最大值。

输入格式

• 第 1 行：n、k
• 第 2 行：n 个整数

输出格式

n-k+1 个整数，为每个窗口的最大值（空格分隔）。

示例

示例 1

输入：

10 3
2 13 6 19 15 13 17 9 19 13

输出：

13 19 19 19 17 17 19 19

说明： 窗口大小为 3，共 8 个窗口，依次输出每个窗口最大值。

---

解题思路

第一步：理解问题本质

窗口从数组左端向右滑动，每移动一位就有一个元素进、一个元素出，要求实时输出窗口内最大值。朴素做法每个窗口扫描一遍。

第二步：暴力解法（每窗口扫描）

对每个窗口（共 n-k+1 个），遍历窗口内 k 个元素求最大值。

for left in range(n - k + 1):
    print(max(arr[left:left + k]), end=' ')

问题：复杂度 O(n·k)，当 n、k 都很大时超时。

第三步：优化解法（单调队列）

用单调递减双端队列维护候选最大值的下标。队列从队头到队尾对应值单调递减，队头始终是当前窗口内最大值。

出队规则：

1. 队头下标滑出窗口（< left）时弹出
2. 新元素入队前，弹出所有比它小的队尾（它们不可能是后续窗口的最大值）

from collections import deque
dq = deque()
for i, v in enumerate(arr):
    if dq and dq[0] < i - k + 1:      # 队头滑出窗口
        dq.popleft()
    while dq and arr[dq[-1]] <= v:    # 弹出比当前值小的队尾
        dq.pop()
    dq.append(i)
    if i >= k - 1:                     # 窗口形成后记录队头
        res.append(str(arr[dq[0]]))

第四步：最优解法

每个元素至多入队一次、出队一次，整体复杂度 O(n)，是最优解法。

---

完整代码实现

算法可视化 · 逐帧回放这道题的代码81 帧 · 录制输入

import sys
from collections import deque


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    arr = list(map(int, data[2:2 + n]))

    dq = deque()      # 存下标，队列从队头到队尾对应值单调递减
    res = []
    for i, v in enumerate(arr):
        # 队头滑出窗口
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        # 弹出所有比当前值小的队尾
        while dq and arr[dq[-1]] <= v:
            dq.pop()
        dq.append(i)
        # 窗口形成后记录队头
        if i >= k - 1:
            res.append(str(arr[dq[0]]))

    print(' '.join(res))


if __name__ == "__main__":
    solve()

---

示例推演

以示例 1 为例，n=10、k=3，数组下标 0~9 对应值 [2, 13, 6, 19, 15, 13, 17, 9, 19, 13]。

逐下标处理（队列存下标，值单调递减，队头为当前窗口最大值）：

• i=0 值 2：队列空，入队 → [0]。i<2 窗口未形成
• i=1 值 13：弹出队尾 2，入队 → [1]。未形成
• i=2 值 6：6<13 直接入队 → [1,2]。窗口形成，队头下标 1 值 13 → 输出 13
• i=3 值 19：弹出 6、13，入队 → [3]。队头值 19 → 输出 19
• i=4 值 15：入队 → [3,4]。队头值 19 → 输出 19
• i=5 值 13：入队 → [3,4,5]。队头值 19 → 输出 19
• i=6 值 17：弹出队尾 13，入队 → [3,4,6]。队头值 19 → 输出 19
• i=7 值 9：队头下标 3 已滑出窗口（3 < 7-3+1=5），弹出 → [4,6]；9<17 直接入队 → [4,6,7]。队头下标 6 值 17 → 输出 17
• i=8 值 19：弹出 9、17、15，入队 → [8]。队头值 19 → 输出 19
• i=9 值 13：13<19 直接入队 → [8,9]。队头值 19 → 输出 19

逐窗口输出为：13, 19, 19, 19, 17, 17, 19, 19。

完整输出 13 19 19 19 17 17 19 19，正确。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力扫描	O(n·k)	O(1)	每窗口扫描 k 个
单调队列	O(n)	O(k)	每元素入队出队各一次

n 为数组长度，k 为窗口大小

---

易错点总结

1. 忘记弹出滑出窗口的队头

队头下标 < i-k+1 时必须 popleft()，否则会输出已滑出窗口的过期元素。

2. 单调队列方向搞反

要维护的是单调递减（队头最大）。若用 >= 弹出相等的队尾，会让同值元素被淘汰，可能影响正确性，通常用 <= 保证新元素优先。

3. 窗口未形成时输出

在 i < k-1 时窗口还没完全形成，此时不能输出队头。必须等到 i >= k-1 才记录。

---

扩展思考

• 单调队列是"滑动窗口最值"的标准模板，同样可求窗口最小值（改为维护单调递增队列）。
• 与单调栈思想相通，都是通过维护单调性来减少无效比较。

---

相关题目

• HJ178. 【模板】双指针