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;
}