最敏捷的机器人

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

单调队列滑动窗口

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1542
// 题意：n 个数、窗口长 k；输出每个连续 k 个数中最大值与最小值；共 n-k+1 行。
// 思路：两个单调队列在 O(n) 内求出每个窗口的最大、最小值。
// 复杂度：O(n) 时间 / O(n) 空间
// 易错点：窗口滑出时及时从队头移除；输出顺序为 最大 最小。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int a[MAXN];
int main(){
    int n,k;
    if(!(cin>>n>>k))return 0;
    for(int i=1;i<=n;i++)cin>>a[i];
    deque<int> mx,mn;
    for(int i=1;i<=n;i++){
        while(!mx.empty()&&a[mx.back()]<=a[i])mx.pop_back();
        while(!mn.empty()&&a[mn.back()]>=a[i])mn.pop_back();
        mx.push_back(i);mn.push_back(i);
        if(i-k>=1){
            if(mx.front()==i-k)mx.pop_front();
            if(mn.front()==i-k)mn.pop_front();
        }
        if(i>=k)cout<<a[mx.front()]<<" "<<a[mn.front()]<<"\n";
    }
    return 0;
}

最敏捷的机器人

正文

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