AcWing - 滑動視窗(單調隊列)

題目連結:https://www.acwing.com/problem/content/description/156/

時/空限制：1s / 64MB

題目描述

給定一個大小為n≤106的數組。

有一個大小為k的滑動視窗，它從數組的最左邊移動到最右邊。

您隻能在視窗中看到k個數字。

每次滑動視窗向右移動一個位置。

以下是一個例子：

該數組為[1 3 -1 -3 5 3 6 7]，k為3。

視窗位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3
1 3 [-1 -3 5] 3 6 7		5
1 3 -1 [-3 5 3] 6 7
1 3 -1 -3 [5 3 6] 7		6
1 3 -1 -3 5 [3 6 7]		7

您的任務是确定滑動視窗位于每個位置時，視窗中的最大值和最小值。

輸入格式

輸入包含兩行。

第一行包含兩個整數n和k，分别代表數組長度和滑動視窗的長度。

第二行有n個整數，代表數組的具體數值。

同行資料之間用空格隔開。

輸出格式

輸出包含兩個。

第一行輸出，從左至右，每個位置滑動視窗中的最小值。

第二行輸出，從左至右，每個位置滑動視窗中的最大值。

輸入樣例

8 3

1 3 -1 -3 5 3 6 7

輸出樣例

解題思路

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
struct Queue {
    int data[MAXN];
    int front_, rear;
    Queue() {
        front_ = 0, rear = -1;
    }
    void push(int x) {
        data[++rear] = x;
    }
    void pop_front() {
        front_++;
    }
    void pop_back() {
        rear--;
    }
    int front() {
        return data[front_];
    }
    int back() {
        return data[rear];
    }
    int size() {
        return rear - front_ + 1;
    }
    bool empty() {
        return rear < front_;
    }
}Qmin, Qmax;
int cnt_max = 0, cnt_min = 0;
int spt[MAXN], res_max[MAXN], res_min[MAXN];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &spt[i]);
    for (int i = 1; i <= n; i++) {
        while (!Qmax.empty() && Qmax.front() + m - 1 < i)
            Qmax.pop_front();
        while (!Qmin.empty() && Qmin.front() + m - 1 < i)
            Qmin.pop_front();
        while (!Qmax.empty() && spt[Qmax.back()] <= spt[i])
            Qmax.pop_back();
        while (!Qmin.empty() && spt[Qmin.back()] >= spt[i])
            Qmin.pop_back();
        Qmax.push(i), Qmin.push(i);
        res_max[++cnt_max] = Qmax.front();
        res_min[++cnt_min] = Qmin.front();
    }
    for (int i = m; i <= n; i++)
        printf("%d%c", spt[res_min[i]], "\n "[i != n]);
    for (int i = m; i <= n; i++)
        printf("%d%c", spt[res_max[i]], "\n "[i != n]);
    return 0;
}