首页 > 试题广场 >

【模板】滑动窗口

[编程题]【模板】滑动窗口

热度指数：2144 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个长度为 $n$ 的整数数组 $a$ 和一个窗口大小 $k$ $(1\leqq k\leqq n)$ 。滑动窗口从左到右移动，每次右移一位（窗口覆盖下标 $[i,i+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

输出

算法知识视频讲解

牛客487544150号

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    while (cin >> n >> k) {
        vector<int> aIntVec(n);
        for (int i = 0; i < n; i++) {
            cin >> aIntVec[i];
        }
        //
        int leftIndex = 0;
        int rightIndex = 0;
        // 更新窗口有边界更新最大值
        for (int i = 0; i < n; i++) {
            leftIndex = i;
            rightIndex = leftIndex + k - 1;
            int maxValue = 0;
            int maxIndex = 0;
            if (rightIndex >= n) {
                break;
            }
            for (int j = leftIndex; j <= rightIndex; j++) {
                if (maxValue < aIntVec[j]) {
                    maxValue = aIntVec[j];
                    maxIndex = rightIndex;
                }
            }
            if (rightIndex < n) {
                cout << maxValue << " ";
            }
        }
    }
}

发表于 2025-12-13 15:27:45 回复(0)

人生有三乐

#include <stdio.h>

#include <stdlib.h>

int main() {

//这题是给一个固定的窗口，每次找这个窗口的最大值，好像挺简单的

int n, k;

scanf("%d %d", &n, &k);

int *array=malloc(sizeof(int)*n);

for(int i=0;i<n;i++)

{

scanf("%d", &array[i]);

//printf("%d ", array[i]);

}

//双指针划出一个固定窗口

for(int i=0;i+k<=n;i++)

{

int max=0;//记录最大值

for(int j=i;j<i+k;j++) //在这个窗口里找最大值

{

if(array[j]>max)

{

max=array[j];

}

printf("%d ",max);

}

return 0;

}

发表于 2025-10-03 14:34:50 回复(0)

Leibnezz

单调双端队列加双指针

发表于 2025-10-01 01:16:59 回复(0)

mock1

import sys

from collections import deque

def getMax(length: int, size: int, li: list) -> str:

result = []

q = deque()

for i in range(length):

while q and li[i] >= li[q[-1]]:

q.pop()

q.append(i)

if q[0] <= i - size:

q.popleft()

if i >= size - 1:

result.append(str(li[q[0]]))

return " ".join(result)

if __name__ == "__main__":

n, k = map(int, sys.stdin.readline().split())

a = list(map(int, sys.stdin.readline().split()))

print(getMax(n, k, a))

发表于 2025-09-25 21:31:22 回复(0)

Python3

牛客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)

Java

六路折梅手

import java.util.*;

import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        String[] lineone=bf.readLine().split(" ");
        String[] linetwo=bf.readLine().split(" ");
        int n=Integer.parseInt(lineone[0]),k=Integer.parseInt(lineone[1]);
        int[] arr=Arrays.stream(linetwo).mapToInt(Integer::parseInt).toArray();
        Deque<Integer> dq=new LinkedList<>();//维护单调队列
        StringJoiner sj=new StringJoiner(" ");

        for(int i=0;i<n;i++){
            //单调递减
            while(!dq.isEmpty()&&arr[dq.peekLast()]<=arr[i]){
                dq.pollLast();//队尾安全出队
            }
            dq.offerLast(i);

            //如果队首划过窗口则移除
            if(dq.peekFirst()<=i-k){
                dq.pollFirst();
            }

            //够窗口大小时收集元素
            if(i>=k-1){
                sj.add(arr[dq.peekFirst()]+"");
            }
        }
        System.out.println(sj.toString());
        
    }
}

发表于 2025-08-24 18:05:55 回复(0)

提交观点

问题信息

双指针

难度：

6条回答 39收藏 303浏览

【模板】滑动窗口

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

相关试题