單調(diào)隊(duì)列

• 利用雙端隊(duì)列實(shí)現(xiàn)
• • 初始化雙端隊(duì)列
  • 維護(hù)隊(duì)頭是最大元素
  • 維護(hù)隊(duì)頭是最小元素
• 利用數(shù)組實(shí)現(xiàn)
• • 維護(hù)隊(duì)頭是最大元素

顧名思義，就是用一點(diǎn)巧妙的方法，使得隊(duì)列中的元素全是單調(diào)遞增或遞減，常常用來(lái)解決滑動(dòng)窗口的一系列問(wèn)題。
好了，廢話不多說(shuō)，上正題。
模板思路在代碼中，超詳細(xì)，看完你就悟了。

利用雙端隊(duì)列實(shí)現(xiàn)

初始化雙端隊(duì)列

void init() {//必須從前邊刪while (!q1.empty()) q1.pop_front();while (!q2.empty()) q2.pop_front();}

維護(hù)隊(duì)頭是最大元素

k是區(qū)間范圍。

struct node{int order;//對(duì)應(yīng)下標(biāo)int value;//對(duì)應(yīng)值 }tmp; deque<node>vis; int main() {int n,k,t;scanf("%d%d",&n,&k);for(int i=0;i<n;i++){scanf("%d",&t);//當(dāng)前值// 當(dāng)隊(duì)列不為空，i是當(dāng)前值得小標(biāo)與隊(duì)頭元素下標(biāo)之差大于等于k//表明，雖然你隊(duì)頭大，但是已經(jīng)不在有效范圍了，所以要丟掉if(!vis.empty() && i-vis.front().order>=k) vis.pop_front();// 隊(duì)列不為空，因?yàn)橐S護(hù)的隊(duì)列是隊(duì)頭是最大的，那么這個(gè)隊(duì)列就//是一個(gè)遞減隊(duì)列（想一下），所以當(dāng)前值要比隊(duì)尾小才可以，//否則就將隊(duì)尾元素丟掉，直到隊(duì)尾比當(dāng)前值小，或隊(duì)列為空while(!vis.empty() && vis.back().value<=t) vis.pop_back();tmp.order=i;tmp.value=t;vis.push_back(tmp);if(i>=k-1){printf("%d\n",vis.front().value);}} }

維護(hù)隊(duì)頭是最小元素

```cpp struct node{int order;//對(duì)應(yīng)下標(biāo)int value;//對(duì)應(yīng)值 }tmp; deque<node>vis; int main() {int n,k,t;scanf("%d%d",&n,&k);for(int i=0;i<n;i++){scanf("%d",&t);//當(dāng)前值if(!vis.empty() && i-vis.front().order>=k) vis.pop_front();// 其余都一樣，只不過(guò)下面這一行，變成當(dāng)前值要大于隊(duì)尾，//結(jié)合上面想想就出來(lái)了，因?yàn)槭且S護(hù)一個(gè)遞增隊(duì)列嘛while(!vis.empty() && vis.back().value>=t) vis.pop_back();tmp.order=i;tmp.value=t;vis.push_back(tmp);if(i>=k-1){printf("%d\n",vis.front().value);}} }

利用數(shù)組實(shí)現(xiàn)

維護(hù)隊(duì)頭是最大元素

vector<int> maxSlidingWindow(vector<int>& nums, int k) {//存的是下標(biāo)vector<int> q(nums.size(),0); vector<int> vec;int tail = 0;//隊(duì)尾指針int head = 0;//隊(duì)頭指針for(int i = 0;i< nums.size();i++){//淘汰操作//和上邊對(duì)比下，隊(duì)列不為空，不就是隊(duì)尾指針大于隊(duì)頭指針嘛//nums[i] 當(dāng)前值，nums[q[tail-1]] 隊(duì)尾值// 丟掉隊(duì)尾元素，不就是將隊(duì)尾指針前移嘛while(tail > head && nums[i] >= nums[q[tail-1]]) tail--;//尾插操作q[tail++] = i;//過(guò)期頭刪操作//q[head] 不就是對(duì)首小標(biāo)嘛if(i - q[head] >= k) head++;if(i >= k) vec.push_back(nums[q[head]]);}return vec;}

看到這里大家有沒(méi)有枉然大悟呀

總結(jié)

以上是生活随笔為你收集整理的单调队列（一套模板通吃）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。