怎么O(n)也T两个点啊！！！！！！！！

yc_baby @ 2024-08-19 11:31:11

by Osamu_Dazai @ 2024-08-22 11:18:36

@13377539482a

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005];
deque<int>st;
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    printf("0\n");
    if(n==1) {
        return 0;
    }
    for(int i=1; i<=n-1; i++) {
        while(!st.empty()&&a[st.back()]>a[i])   st.pop_back();
        st.push_back(i);
        while(!st.empty()&&st.front()<=i-m) st.pop_front();
        printf("%d\n",a[st.front()]);
    }
    return 0;
}

by Osamu_Dazai @ 2024-08-22 11:19:03

求关注！！！

by Osamu_Dazai @ 2024-08-22 11:20:02

数组大小开到10000005，不然RE两个点

by yc_baby @ 2024-08-31 21:32:08

@HarryPotter888 给你关注

by yc_baby @ 2024-08-31 21:39:21

@HarryPotter888 我刚刚又提交了一次上次的超时代码，结果过了。真玄学！