154. 滑动窗口【单调队列】

妖狐艹你老母 2022-01-06 07:27 249阅读 0赞

# 滑动窗口 #

## 问题描述 ##

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

## 题解 ##

维护一个单调队列，

假如我们先求最小值，保证队首就是最小值，满足滑动窗口长度时输出队首；

例如样例 1 3 -1 -3 5 3 6 7

第一步 1 先入队了

第二步  1 小于3 没问题 所以3接着入队了

第三步   1和3 都大于-1 所以1和3都弹出  -1入队  此时刚好满足长度为k（k=3）的滑动窗口，输出队首 -1

第四步  -1 大于 -3 所以-1弹出 -3 入队  输出队首-3

第五步 -3 小于5 没问题  5入队 输出队首-3

第六步  5大于3  那5不论怎么样都不可能是最小值了，所以弹出5  ，3入队，输出队首-3

第六步  3小于6没问题  6入队，此时滑动窗口覆盖范围已经走到了（5,3,6） 所以要将-3 出队，输出队首3

第七步 6小于7没问题   ，7入队，输出队首3

求最大值的话同理

## 代码 ##

#include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    #define readc(x) scanf("%c",&x)
    #define read(x) scanf("%d",&x)
    #define read2(x,y) scanf("%d%d",&x,&y)
    #define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define print(x) printf("%d\n",x)
    #define mst(a,b) memset(a,b,sizeof(a))
    #define pb push_back
    #define mp make_pair
    const int maxn = 1e6 + 5;
    int a[maxn];
    struct node {
      int v; //值
      int index ; //下标
    }que[maxn];
    int main(){
      int n,k;
      read2(n,k);
      for(int i = 1 ; i <= n; i++){
          read(a[i]);
      }
      int head = 1;
      int tail = 0;
      for(int i = 1 ; i <= n; i++){
        while(head <= tail && que[tail].v >= a[i])
             tail--;           //如果队列中的数大于要入队的数，就全补弹出
        que[++tail].v = a[i];  que[tail].index = i;      //入队
        if(i - k >= que[head].index)  head++;          //超出窗口的长度，弹出队首
        if(i >= k) {           // 前k-1个无法形成滑动窗口
          printf("%d",que[head].v);
          if(i != n) printf(" ");
        }
      }
      printf("\n");
      head = 1,tail = 0;
      for(int i = 1 ; i <= n; i++){
        while(head <= tail && que[tail].v <= a[i]) tail--;
        que[++tail].v = a[i];  que[tail].index = i;
        if(i - k >= que[head].index)  head++;
        if(i >= k) {
          printf("%d",que[head].v);
          if(i != n) printf(" ");
        }
      }
      printf("\n");
    }

转载于:https://www.cnblogs.com/llke/p/10780121.html