题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
deque<int>maxq;
deque<int>minq;
int a[N];
int n,k;
#define SX
#ifdef SXH
    #define debug printf("第%d行\n",__LINE__)
    #define print(name,a) cout<<name<<": "<<a<<endl
#else
    #define debug //
    #define print(name,a) //
#endif
int maxq_push(int i) {
    //优化 
    while(!maxq.empty()&&a[maxq.back()]<=a[i]){
        print("max出队",a[maxq.back()]);
        maxq.pop_back();
    }
    maxq.push_back(i);
    print("max入队",a[i]);
    //限制大小 
    print("back",maxq.back());
    print("front",maxq.front());

    while((maxq.back()-maxq.front() + 1) > k){
    maxq.pop_front();
    print("back",maxq.back());
    print("front",maxq.front());
    }
    return maxq.front();
}
int minq_push(int i) {
    //优化 
    while(!minq.empty()&&a[minq.back()]>=a[i]){
        print("min出队",a[minq.back()]);
        minq.pop_back();
    }
    minq.push_back(i);
    print("min入队",a[i]);
    //限制大小 
    print("back",minq.back());
    print("front",minq.front());

    while((minq.back()-minq.front() + 1) > k){
    minq.pop_front();
    print("back",minq.back());
    print("front",minq.front());
    }
    return minq.front();
}

int main() {
    scanf("%d%d",&n,&k);
    for(int i = 0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    //维护一个最大队列
    //维护一个最小队列
    /*在最大队列中
    靠前并且较小的元素
    应该被删除
    因为竞争力不如靠后且较大的元素
    */
    for(int i = 0;i<(k-1);i++){
        minq_push(i);
        maxq_push(i);
    }
    for(int i = k-1;i<n; i++) {
        printf("%d ",a[minq_push(i)]);
    }
    printf("\n");
    for(int i = k-1;i<n; i++) {
        printf("%d ",a[maxq_push(i)]);
    }
    printf("\n");
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla