【滑動視窗最值】滑動視窗的最值的一種方案

　　假設現在有數組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) 成功減少了時間複雜度。

另：有儲存下標來刪除滑動視窗的做法。