[牛客每日一題] (單調隊列) NC50528 滑動視窗

​​滑動視窗 (nowcoder.com)

https://ac.nowcoder.com/acm/problem/50528​​

題目描述

給一個長度為N的數組，一個長為K的滑動窗體從最左端移至最右端，你隻能看到視窗中的K個數，每次窗體向右移動一位，如下圖：

你的任務是找出窗體在各個位置時的最大值和最小值。

輸入描述:

第1行：兩個整數N和K；

第2行：N個整數，表示數組的N個元素(≤2×10^9)；

輸出描述:

第一行為滑動視窗從左向右移動到每個位置時的最小值，每個數之間用一個空格分開；

第二行為滑動視窗從左向右移動到每個位置時的最大值，每個數之間用一個空格分開。

示例1

輸入

8 3

1 3 -1 -3 5 3 6 7

輸出

-1 -3 -3 -3 3 3

3 3 5 5 6 7

備注:

對于20%的資料，K≤N≤1000；

對于50%的資料，K≤N≤10^5；

對于100%的資料, K≤N≤10^6。

以最大值舉例,

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

const int N = 1e6+10;
int a[N],q[N];
int main()
{
    int n, k;
    cin >> n >> k;
    
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    
    int front = 0, rear = -1;
    
    for(int i = 1; i <= n; i ++)
    {
        //去除閑雜元素
        if(front <= rear && i-k+1 > q[front]) front++;
        //優勝劣汰
        while(front <= rear && a[i] < a[q[rear]]) rear--;
        
        q[++rear] = i;
        if(i >= k) printf("%d ", a[q[front]]);
    }
    cout << endl;
    front = 0, rear = -1;
    
    for(int i = 1; i <= n; i ++)
    {
       if(front <= rear && i-k+1 > q[front]) front++;
        while(front <= rear && a[i] >= a[q[rear]]) rear--;
        q[++rear] = i;
        if(i >= k) printf("%d ", a[q[front]]);
    }
    return 0;
}