单调队列区间问题
查看原帖
单调队列区间问题
452138
137292zW楼主2022/1/19 11:18

1.为什么单调队列要小于n - 1 而不是 n 2.前m个数到它本身,不是 队列第一个数 到 它本身, 个数应该 +1,应该小于 i 吗?

#include<iostream>
#include<deque>
using namespace std;

deque<int> q;
int a[3000005];

int main(){
    
    int n, m;
    cin >> n >> m;
    
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    
    cout << 0 << endl;
    
    for(int i = 0; i < n - 1; i++){//这里
        if(q.size() && q.front() + m <= i//这里)
            q.pop_front();
        while(q.size() && a[i] <= a[q.back()])
            q.pop_back();
        q.push_back(i);
        printf("%d\n", a[q.front()]);
    }
    
    return 0;
}
2022/1/19 11:18
加载中...