C++单调队列实现滑动窗口（数组实现队列）

本文主要是介绍C++单调队列实现滑动窗口（数组实现队列），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目来源AcWing第154题

题目

给定一个大小为 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

解题思路

首先根据滑动窗口数据进出的特殊性我们很容易想到用队列来最这题。然后题目要求求最值，则想到了单调队列。滑动窗口（队列）在数组中滑动，然后队头出队，再数据入队列前判定队头是否比当前数大（或者小），是的话就出队。数据入队后输出队头就是要求的最值。

代码

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], queue[N]; //a[N]为数组长度，queue[N]为队列
int n, k; //n为数组总长度，k为队列长度

int main(){
    scanf("%d%d", &n,&k);
    for(int i = 0;i < n; i++) scanf("%d", &a[i]); 

    int head = 0, tail = -1; //head为队列头指针，tail为队列尾指针,队列初始化
    for(int i = 0; i < n; ++ i ){
        //队列不为空，且滑动窗口还没走到最后，队首走出窗口
        if(head <= tail && queue[head] < i - k +1) head ++;
        //队列不为空，且队头元素比当前数大，出队
        while(head <= tail && a[queue[head]] >= a[i]) tail --;
        queue[++ tail] = i; //当前数从队尾入队
        //从第一个窗口开始，数组已经遍历到第k个数的时候，输出队头元素(此时队头元素就是最小值)
        if(i >= k - 1) printf("%d ", a[queue[head]]); 
    }
    printf("\n");
    //求最大值也是相同道理，head为队列头指针，tail为队列尾指针,队列初始化
    head = 0, tail = -1;
    for(int i = 0; i < n; ++ i ){
        if(head <= tail && queue[head] < i - k +1) head ++;
        while(head <= tail && a[queue[head]] <= a[i]) tail --;
        queue[++ tail] = i; 
        if(i >= k - 1) printf("%d ", a[queue[head]]); 
    }

    return 0;
}

这篇关于C++单调队列实现滑动窗口（数组实现队列）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！