牛客每日一题3.30 滑动窗口 单调队列

https://blog.csdn.net/qq_43804974/article/details/105176524
这道题由于空间限制的很死，所以原本用线段树之类O(nlogn)的算法都会MLE，唯一的做法就是O（N）的单调队列。

对于每一个滑动窗口的元素，都是从上一个窗口的基础上，增加一个新的元素，减掉一个最后的元素。就利用单调双端队列去处理问题，对于一个新的窗口就push进去，然后不断pop直到出现第一个合法的元素，那个元素就是我们要的这个窗口内的最值的答案，不合法的元素是什么意思呢，就是你这个元素所在的位置太前了， 这个窗口的区间包含不到他，所以只能删掉。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<time.h>
#include<string>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#define ll long long
#define double long double
using namespace std;
#define PI  3.1415926535898
#define eqs 1e-17
const long long max_ = 1e6 + 7;
int mod = 2014;
const int inf = 1e9 + 7;
const long long INF = 1e18;
int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while (ch<'0' || ch>'9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0'&&ch <= '9') {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}
inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline int min(int a, int b) {
    return a < b ? a : b;
}
inline int max(int a, int b) {
    return a > b ? a : b;
}
pair<int, int> quemax[max_];
pair<int, int> quemin[max_];
int qmaxL = 1, qmaxR = 0, qminL = 1, qminR = 0;
int n, node[max_],k;
int ansmax[max_], ansmin[max_],an = 0;
signed main() {
    n = read(),k = read();
    for (int i = 1; i <= n; i++) {
        node[i] = read();
    }
    quemax[++qmaxR] = make_pair(node[1], 1);
    quemin[++qminR] = make_pair(node[1], 1);
    for (int i = 2; i <= k; i++) {
        while (qmaxL <= qmaxR && quemax[qmaxR].first < node[i])qmaxR--;
        quemax[++qmaxR] = make_pair(node[i], i);

        while (qminL <= qminR && quemin[qminR].first > node[i])qminR--;
        quemin[++qminR] = make_pair(node[i], i);

    }
    ansmax[++an] = quemax[qmaxL].first, ansmin[an] = quemin[qminL].first;

    for (int i = k + 1; i <= n; i++) {
        //[i - k + 1,i]
        while (qmaxL <= qmaxR && quemax[qmaxR].first < node[i])qmaxR--;
        quemax[++qmaxR] = make_pair(node[i], i);
        while (qmaxL <= qmaxR && quemax[qmaxL].second < i - k + 1)qmaxL++;

        while (qminL <= qminR && quemin[qminR].first > node[i])qminR--;
        quemin[++qminR] = make_pair(node[i], i);
        while (qminL <= qminR && quemin[qminL].second < i - k + 1)qminL++;

        ansmax[++an] = quemax[qmaxL].first, ansmin[an] = quemin[qminL].first;
    }
    for (int i = 1; i <= an; i++) {
        cout << ansmin[i] << " ";
    }
    cout << endl;
    for (int i = 1; i <= an; i++) {
        cout << ansmax[i] << " ";
    }

    return 0;
}