CSDN

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

2023-12-15 16:35 由 意外路过的番茄酱骑士 发表于 #后端开发

　　假设现在有数组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]);
    }
    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;
}

　　那么久只剩一个问题了，为什么时间复杂度减少到了O(n*logn) 看起来while循环很多对吧，其实我们换个角度考虑问题，每个元素最多入队4次，出队4次，

　　我们一共有n个元素消耗时间T(4*n) 插入的时间复杂度时O(logn) 那么时间复杂度为O(nlogn) 成功减少了时间复杂度。

 

另：有储存下标来删除滑动窗口的做法。

热门相关：无上崛起   陆鸣至尊神殿   魔葫   我有一张均富卡   仙王