第一问，时间复杂度真比nk小吗？
是的，就算某一次i出现队列全满一个个pop掉，下一个队列未满肯定要少。
第二问，既是为什么出队列要-k着看，也是为什么大于k每个都要pop？
因为，你可以多但不能少，每次cout完队列一直pop维护，从前面开始只要是过框的就出了，后面不会有数值相同位置不同的情况或者是余孽。

#include <bits/stdc++.h>
using namespace std;
int a[1000010];
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    deque <int> q;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<n;i++){
        while(q.size()&&a[i]<q.back()){
            q.pop_back();
        }
        q.push_back(a[i]);      
        if(i>=k-1) cout<<q.front()<<' ';   
        if(i>=k-1&&q.front()==a[i-k+1]) q.pop_front();
    }
    printf("\n");
    q.clear();
    for(int i=0;i<n;i++){
        while(q.size()&&a[i]>q.back()){
            q.pop_back();
        }
        q.push_back(a[i]);      
        if(i>=k-1) cout<<q.front()<<' ';   
        if(i>=k-1&&q.front()==a[i-k+1]) q.pop_front();
    }
    return 0;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla