(滑动窗口)acwing154. 滑动窗口算法基础班第二讲

题目

给定一个大小为 n≤106 的数组。

有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

输入格式
输入包含两行。

第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式
输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

8 3
1 3 -1 -3 5 3 6 7

输出样例：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

分析

解读题意：给定一个n，k，n为数组的长度，k为滑动窗口的长度，要求每个滑动窗口中找出一个最大值和一个最小值，如果用暴力的做法，每次循环一遍窗口中的所有元素，时间复杂度为O（nk）大概率会超时，我们想一想窗口中的哪些元素对我们判断最小值没有作用，例如现在滑动窗口中的元素为5 6 -1，现在我们要找最小值，-1在5 6的右边，会比5 6后弹出队列，且-1小于5 6，所以这个时候5 6就是对我们判断结果没有作用

代码部分

#include <bits/stdc++.h>
using namespace std;

void fast()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
}

const int N=1e6+10;
int a[N],p[N];
int hh=0,tt=-1;

int main (void)
{
    fast();
    int n,k;
    cin>>n>>k;
    
    for(int i=0;i<n;i++)    cin>>a[i];
    
    for(int i=0;i<n;i++)
    {
        if(hh<=tt&&i-k+1>p[hh]) hh++;
        while(hh<=tt&&a[p[tt]]>=a[i]) tt--;
        
        p[++tt]=i;
        if(i-k+1>=0)	cout<<a[p[hh]]<<' ';
    }
    cout<<endl;
    
    int hh=0,tt=-1;
    for(int i=0;i<n;i++)
    {
    	if(hh<=tt&&i-k+1>p[hh])	hh++;
    	while(hh<=tt&&a[p[tt]]<=a[i])	tt--;
    	
    	p[++tt]=i;
    	if(i-k+1>=0)	cout<<a[p[hh]]<<" ";
	}
	
    
    return 0;
    
}

总结

看似是队列，其实我感觉更偏向于双指针，因为它要在队尾删除元素，理解模板之后，要做到倒背如流

May you succeed