滑动窗口

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1322 字

长度为N的数组，窗口长K从左滑到右，求每个窗

一本通
例

正文

/*
原题：T1597 「一本通 5.5 例 1」滑动窗口
题意：长度为 N 的数组，窗口长 K 从左滑到右，求每个窗口内的最小值与最大值。
思路：两个单调队列分别维护最小、最大值：队首为窗口最优，入队时从队尾弹出不优元素（去尾），
     队首下标超出窗口左边界则出队（去头）。扫描一遍即可。
复杂度：时间 O(N)，空间 O(N)。
易错点：输出分两行（先最小后最大）；K 可能等于 N；队中存下标以便判断越界。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    deque<int> q;
    vector<int> mn;
    for(int i=0;i<n;i++){
        while(!q.empty()&&a[q.back()]>=a[i]){
            q.pop_back();
        }
        q.push_back(i);
        if(q.front()<=i-k){
            q.pop_front();
        }
        if(i>=k-1){
            mn.push_back(a[q.front()]);
        }
    }
    q.clear();
    vector<int> mx;
    for(int i=0;i<n;i++){
        while(!q.empty()&&a[q.back()]<=a[i]){
            q.pop_back();
        }
        q.push_back(i);
        if(q.front()<=i-k){
            q.pop_front();
        }
        if(i>=k-1){
            mx.push_back(a[q.front()]);
        }
    }
    for(int i=0;i<(int)mn.size();i++){
        if(i){
            cout<<' ';
        }
        cout<<mn[i];
    }
    cout<<'\n';
    for(int i=0;i<(int)mx.size();i++){
        if(i){
            cout<<' ';
        }
        cout<<mx[i];
    }
    cout<<'\n';
    return 0;
}

滑动窗口

正文

一本通·提高篇的其它内容