题目描述C语言版本

blablabla

样例

#include<stdio.h>

#define max 1000010

int arr[max],deque[max],t,h;
int n;


int main(){
    int k;
    scanf("%d%d",&n,&k);
    t=0,h=0;
    for(int i=0;i<n;++i)scanf("%d",&arr[i]);
    //最小值
     for(int i=0;i<k-1;++i){
        while(h<t&&arr[deque[t-1]]>=arr[i])t--;
        deque[t++]=i;
     }
     int m=n-k+1;
     int res[m];
     for(int l=0,r=k-1;l<m;++l,++r){
        while(h<t&&arr[deque[t-1]]>=arr[r])t--;
        deque[t++]=r;
        res[l]=arr[deque[h]];
        if(deque[h]==l)h++;
     }
     for(int i=0;i<m;++i)printf("%d ",res[i]);
     printf("\n");
    h=0,t=0;
    //最大值 
    for(int i=0;i<k-1;++i){
        while(h<t&&arr[deque[t-1]]<=arr[i])t--;
        deque[t++]=i;
    }
    //int m=n-k+1;
    int ans[m];
    for(int l=0,r=k-1;l<m;++l,++r){
        while(h<t&&arr[deque[t-1]]<=arr[r])t--;
        deque[t++]=r;
        ans[l]=arr[deque[h]];
        if(deque[h]==l)h++;

    }
    for(int i=0;i<m;++i)printf("%d ",ans[i]);

    return 0;


}
blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla