题目大意

给定长为n的整数序列a[],求每一个长度为k的子串中的最大值和最小值

解题思路

毕竟人生中第一个单调队列
一开始还以为自己写丑了,但是看了看网上的代码……啊既然大家都这么丑我就放心了。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int N, K;
int a[1000005];
int minq[1000005], h1, t1; //单调递减的队列,用于求最大值
int maxq[1000005], h2, t2; //单调递增的队列,用于求最小值
int Ans_min[1000005];
int Ans_max[1000005];

int main() {
    N=read(); K=read();
    for(int i=1; i<=N; i++) a[i] = read();
    h1 = h2 = 1; t1 = t2 = 0;
    for(int i=1; i<=N; i++) {
        while((h1<=t1) && (minq[h1]+K) <= i) h1++;
        while((h2<=t2) && (maxq[h2]+K) <= i) h2++;
        while((t1>=h1) && (a[i] > a[minq[t1]])) t1--;
        minq[++t1] = i;
        while((t2>=h2) && (a[i] < a[maxq[t2]])) t2--;
        maxq[++t2] = i;
        if(i >= K) {
            Ans_min[i] = a[maxq[h2]];
            Ans_max[i] = a[minq[h1]];
        }
    }
    for(int i=K; i<=N; i++) printf("%d ", Ans_min[i]);
    printf("\n");
    for(int i=K; i<=N; i++) printf("%d ", Ans_max[i]);
    return 0;
}