题目描述

给定一个数组，再给定一个大小为k的滑动窗口，将滑动窗口每次向右滑动时窗口里的最大值和最小值输出

样例

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

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

算法1

单调队列(循环队列)

• 根据输出样例，最小值与最大值是分成两行输出的，所以边输入边输出是不行的(因为要遍历两边，或者遍历一遍但需要一个数组存储最大值)，所以用一个很大的数组来保存输入；
• 由题可知，队列长度最大不会超过窗口大小k，所以这边采用一个单调循环队列来避免队列开很大的空间；
• 因为在队里的元素最大不会超过窗口大小，也即队列大小，队列不会进行判满操作，无需与判空区别开来，所以这里将循环队列预留出来的一个位置取消掉了；
• y总在队列里存的是数组下标，这一操作直接将“如何保证我队列里的元素都是窗口里面的元素”这一大问题解决了，y总牛逼；
• 为什么使用单调队列？因为单调队列会对入队元素进行筛选，如果将入队的元素不符合队里元素排列规则，则将队尾元素排出，直到入队元素符合要求；
• 在本题中，单以求最小值来说，如果将要入队的元素比队尾元素要小，则队尾元素必然不会是滑动窗口的最小值(比新元素先离开滑动窗口，且与该元素同在滑动窗口时还没人家小)，则排出该元素，再进行入队元素与队尾元素的比较，直到能够让此元素入队；

C++ 代码

#include<iostream>
using namespace std;

const int N = 1e6+10;
int a[N];               //用来存储输入的数组；

int main()
{
    std::ios::sync_with_stdio(false);       //给cin提速；

    int n, k;
    cin>>n>>k;
    int q[k];                               //因为不需判满所以设置大小为k的循环队列；
    for(int  i = 0; i < n; ++i) cin>>a[i];

    int head = 0, tail = -1;                //队列头尾指针初始化；
    for(int i = 0; i < n; ++i){
        if(head%k != (tail+1)%k && q[head] < i-k+1) head = (head+1)%k; //队列不空且队头元素离开滑动窗口时队头元素出队；
        while(head%k != (tail+1)%k && a[q[tail]] >= a[i]) tail = (tail-1)%k;//队不空且入队元素比队尾元素要小的时候，队尾元素循环出队；
        tail = (tail+1)%k;      //因为tail指向队尾元素，所以先+1再入队；
        q[tail] = i;

        if(i>=k-1) cout<<a[q[head]]<<' ';       //这里i>=k-1是因为只输出n-k+1个元素
    }
    cout<<endl;
    //求最大值，同上
    head = 0, tail = -1;
    for(int i = 0; i < n; ++i){
        if(head%k != (tail+1)%k && q[head] < i-k+1) head = (head+1)%k;
        while(head%k != (tail+1)%k && a[q[tail]] <= a[i]) tail = (tail-1)%k;
        tail = (tail+1)%k;
        q[tail] = i;

        if(i>= k-1) cout<<a[q[head]]<<' ';
    }

    return 0;
}