BISHI114　【模板】滑动窗口¶

简单通过率 50.01%python3样例通过牛客 AC双指针

牛客原题　源码

讲解章节：单调栈与单调队列、双指针与滑动窗口

一句话

每个长度为 k 的窗口的最大值。

解题思路¶

这题考什么¶

单调队列的裸模板。维护一个下标递增、对应值单调递减的双端队列：

新元素 a[i] 进来时，把队尾所有 <= a[i] 的下标弹掉（它们比 a[i] 小又比 a[i] 早过期，永远不可能再当最大值）；
队首下标 <= i - k 说明已经滑出窗口，弹掉；
队首就是当前窗口最大值。

每个下标最多进队一次、出队一次，总复杂度 O(n)。

数据规模与复杂度¶

n <= 2e5，时限「其他语言 6 秒」，O(n) 非常宽裕。注意 max(a[i:i+k]) 那种「切片 + max」写法虽然是 C 层循环，复杂度仍是 O(nk) = 2e10，不是优化，会 TLE。

坑在哪¶

输出是一行、用单个空格分隔（看样例），不是每行一个；
队首过期判断是 q[0] <= i - k，写成 < 会让窗口变成 k+1 长；样例 2 是 k=1、样例 3 是 k=n，出题人专门给了两个边界，写完必须都测；
队尾弹出用 <=（相等也弹）能让队列更短，本题求最大值两种写法答案相同。

参考实现¶

solutions/BISHI114.py
import sys
from collections import deque


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    a = list(map(int, data[2:2 + n]))
    q = deque()                              # 存下标，对应值单调递减
    res = []
    push = res.append
    for i in range(n):
        x = a[i]
        # 1) 维持单调性：队尾那些 <= x 的下标既比 x 小、又比 x 先过期，
        #    往后任何一个窗口里都轮不到它们当最大值，可以永久丢弃
        while q and a[q[-1]] <= x:           # 队尾比新元素小 -> 永远轮不到它
            q.pop()
        q.append(i)
        # 2) 窗口每次只右移一格，因此最多只有一个下标刚刚滑出去，用 if 而非 while
        if q[0] <= i - k:                    # 队首过期
            q.popleft()
        # 3) i < k-1 时窗口还没填满，从 i = k-1 起每一步恰好对应一个答案
        if i >= k - 1:
            push(a[q[0]])                    # 队首下标对应的值即当前窗口最大值
    sys.stdout.write(" ".join(map(str, res)) + "\n")   # 一行输出，空格分隔


main()

BISHI114 【模板】滑动窗口¶