碼蹄集OJ-大約

#include<bits/stdc++.h> 
using namespace std;
priority_queue<int>max2,maxDel;
priority_queue<int,vector<int>,std::greater<int>>min2,minDel;
const int N=1e5+1;
int n,result=0,a[N];
int main( )
{cin>>n;for(int i=1,j=1;i<=n;i++){cin>>a[i];max2.push(a[i]);min2.push(a[i]);while(max2.top()-min2.top()>1){maxDel.push(a[j]);minDel.push(a[j]);j++;while(!maxDel.empty() &&max2.top()==maxDel.top()){max2.pop();maxDel.pop();}while(!minDel.empty() &&min2.top()==minDel.top()){min2.pop();minDel.pop();}}   result=max(result,i-j+1);}cout<<result;return 0;
}

要想找到滑動窗口的最大值，想到運用雙指針實現滑動窗口，運用大根堆小根堆求出每一個窗口的最大值，最小值。

大根堆小根堆的初始化：

priority_queue<int>max2,maxDel;
priority_queue<int,vector<int>,std::greater<int>>min2,minDel;

定義雙指針i,j。i，j初始指向第一個元素，i依次向后遍歷，同時加入到大根堆和小根堆中，將這兩個堆頭元素相減得到最大值減最小值。

當差值大于一時，循環的將j指針指向的數組值加入maxDel和minDel(因為不確定加入的值為多大)，將j指針向后移一位。同時判斷移除的數影響最大值還是最小值，如果影響最大值，則按照maxDel中數的多少pop出大根堆中的元素。最后輸出結果為滑動窗口的最大值，滑動窗口的大小為i-j+1。

注意：在調用堆（類似隊列）時一定要判空，因為在調用空隊列時會報錯。