首页 > 试题广场 >

【模板】滑动窗口

[编程题]【模板】滑动窗口
  • 热度指数：2225 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个长度为 n 的整数数组 a 和一个窗口大小 k (1\leqq k\leqq n)。滑动窗口从左到右移动，每次右移一位（窗口覆盖下标 [i,i+k-1]）。对于数组的每一个窗口位置，求出窗口内元素的最大值。

输入描述:
\hspace{15pt}第一行输入两个整数 n,k\left(1\leqq k\leqq n\leqq 2\times10^{5}\right)。 
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots ,a_n，元素范围 1 \leqq a_i \leqq 10^{9}。


输出描述:
\hspace{15pt}输出共 n-k+1 个整数，为每个滑动窗口的最大值，数之间以单个空格分隔。
示例1

输入

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

输出

13 19 19 19 17 17 19 19
示例2

输入

10 1
13 13 5 3 9 19 18 4 17 3

输出

13 13 5 3 9 19 18 4 17 3
示例3

输入

10 10
15 20 5 20 19 1 4 18 14 15

输出

20
算法知识视频讲解
添加回答
Python3
牛客847294653号头像 牛客847294653号
from collections import deque

n, k = map(int, input().split())
a = list(map(int, input().split()))

q = deque()  # 存储下标
ans = []
for i,x in enumerate(a):
    #入
    while q and a[q[-1]] <= x:
        q.pop()
    q.append(i)
    #出
    if i - q[0] + 1 > k:
        q.popleft()
    #更新答案
    if i >= k-1:
        ans.append(a[q[0]])
print(*ans)
发表于 2025-08-26 21:23:17 回复(0)
提交观点

问题信息

双指针
难度：
1条回答 320浏览

热门推荐

相关试题

【模板】滑动窗口

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号