【滑动窗口最值】滑动窗口的最值的一种方案-Toy模板网

这篇具有很好参考价值的文章主要介绍了【滑动窗口最值】滑动窗口的最值的一种方案。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

　　假设现在有数组a[n]，和滑动的窗口长度为k <= n，要求长度为k的滑动窗口的最值，一般来说，我们会遇到以下问题：

【滑动窗口最值】滑动窗口的最值的一种方案

　　在窗口向右滑动时，由于不知道将要删除的元素在窗口中的位置，于是只能暴力遍历窗口来删除旧元素。增加了时间复杂度到O(n^2logn)

　　以下是解决该问题的一种方案：

　　使用一个额外的优先队列来储存待删除的元素，等到储存窗口的优先队列的队首元素和待删除元素所在元素相同时就一直删除俩队首，直到一方为空或者队首不再相等，时间复杂度为O(n*logn)

　　相同代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,k;
signed main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>k;
    vector<int> mn;
    vector<int> mx,a(n);
    priority_queue<int> p,q;
    priority_queue<int,vector<int>,greater<int>> p1,q1;
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    
    for(int i = 0; i < k; i++){
        p.push(a[i]);
        p1.push(a[i]);
　　　　//首先创建长度为k的两个滑动窗口
    }
    mx.push_back(p.top());
    mn.push_back(p1.top());
//存下初始状态的答案
    for(int i = k; i < n; i++){
        q.push(a[i - k]);
        q1.push(a[i - k]);
//滑动窗口记录下应该删除的元素
        if(p.size() && q.size()){
            while(p.top() == q.top()){
                p.pop();
                q.pop();
                if(p.empty() || q.empty()) break;
            }
        }
        if(p1.size() && q1.size()){
            while(p1.top() == q1.top()){
                p1.pop();
                q1.pop();
                if(p1.empty() || q1.empty()) break;
            }
        }
        p.push(a[i]);
        p1.push(a[i]);
        mx.push_back(p.top());
        mn.push_back(p1.top());
        
    }
    int len = mx.size();
    for(int i = 0; i < len; i++){
        cout<<mn[i]<<" ";
    }
    cout<<'\n';
    for(int j = 0; j < len; j++){
        cout<<mx[j]<<" ";
    }
    return 0;
}