目錄

單調隊列

使用單調隊列維護滑動窗口

具體過程：

代碼實現：?

復雜度分析：

使用單調隊列優化動態規劃

例題?

---

單調隊列

單調隊列(deque)是一種特殊的隊列，隊列中的元素始終按嚴格遞增或者遞減排列。這樣就可以保證隊頭元素始終是最大值或者最小值。

【問題引入】

有一個數組，長度為n，給你一個區間[left,right]，求出該區間內的最小值或者最大值。

我們如果進行普通的遍歷，最壞的情況下時間復雜度是O(N），遍歷整個數組。

而我們如果用單調隊列來維護這段區間，始終保持隊列的單調性，就可以在O(1)的時間內找到該區間的最大值或者最小值，就是隊頭元素。

【結論】

所以單調隊列的核心用途是高效維護動態窗口的極值（最大值或最小值）。

那么對于一些動態規劃，如轉移方程需要進行一段區間的最值計算，可以使用單調隊列優化。

---

使用單調隊列維護滑動窗口

題目鏈接：239. 滑動窗口最大值 - 力扣（LeetCode）

當窗口形成后，我們需要找到這段窗口中的最大值，暴力的方法就是對這段區間進行遍歷，每個元素進行比較，選出最大值。這樣做時間復雜度為O(N^2)，效率太低。

使用單調隊列優化：單調隊列維護該窗口，隊頭元素為最大元素。時間復雜度為O(N)。

具體過程：

• 創建一個單調對列，維護該隊列的遞減性，以保證對頭元素為窗口中的最小值。
• 對于該單調隊列，存放元素的下標，按值遞減排列。新來一個元素（也就是滑動窗口右移一步），需要判斷對頭元素是否還在窗口內，所以記錄下標，便于判斷對頭元素是否還在窗口中，如果不在，刪除對頭元素。
• 新來一個元素（也就是滑動窗口右移一步），每次都需要比較隊尾元素與當前元素的大小，我們維護的是遞減隊列，如果隊尾元素大于當前元素，則將當前元素的下標直接加入隊列；如果隊尾元素小于當前元素，則將隊尾元素刪除，直到隊尾元素大于當前元素，再將當前元素下標加入隊列，保持隊列的遞減性。
• 窗口形成后，統計結果即可。隊頭元素就是最大元素。

代碼實現：?

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {//雙端隊列 存儲數組索引deque<int> dq;vector<int> res;for(int i=0;i<nums.size();i++){//移除超出范圍的隊首元素while(!dq.empty()&&dq.front()<=i-k)dq.pop_front();//維護隊列遞減性(從隊頭到隊尾)，移除所有小于當前元素的隊尾元素 while(!dq.empty()&&nums[dq.back()]<nums[i])dq.pop_back();//當前元素入隊列dq.push_back(i);//窗口形成后，統計結果，隊頭元素就是最大元素if(i>=k-1)res.push_back(nums[dq.front()]);}return res;}
};

?上面的寫法是使用庫中的deque，還可以使用數組來模擬：

#include<iostream>
using namespace std;
const int N = 1e6 + 5;int a[N], q[N];
int n, k;int main()
{cin >> n >> k;for (int i = 1; i <= n; i++) cin >> a[i];int hh = 0, tt = -1;for (int i = 1; i <= n; i++){while (hh <= tt && i - k >= q[hh]) hh++;//處理隊首while (hh <= tt && a[q[tt]] <= a[i]) tt--;//處理隊尾q[++tt] = i;//隊尾元素加入if (i >= k) cout << a[q[hh]] << " ";//輸出隊首元素}cout << endl;return 0;
}

復雜度分析：

每個元素最多入隊和出隊一次，時間復雜度為O(N)，隊列最多存儲k個元素，時間復雜度為O(K)。?

---

使用單調隊列優化動態規劃

在動態規劃中，當狀態轉移需要在一個窗口查找極值時，可以使用單調隊列優化時間復雜度。

題目鏈接：P5858 「SWTR-3」Golden Sword - 洛谷

狀態表示：dp[i][j]表示加入第i個材料時，?鍋內的材料個數為j（包括此時加入的），此時的耐久度的最大值。

狀態轉移方程的分析：加入第i個材料后的最大耐久度，等于加入第i-1個材料時最大的耐久度，再加上自身的耐久度，也就是再加上a[i]*j。

狀態轉移方程：dp[i][j]=max(dp[i][j],dp[i-1][k]+j*a[i])，j-1<=k<=min(w,j-1+s)。

正常使用動態規劃：

第一層循環遍歷i。

第二層循環遍歷j，填寫dp[i][j]。

但是由于有求[j-1,min(w,j-1+s)]最大值的操作，所以還需一層循環求最大值。

共三層循環，時間復雜度太大，需要進行優化。

#include <iostream>
using namespace std;
long long n, m, s;
long long a[5505];
long long dp[5505][5505];int main()
{cin >> n >> w >> s;for (long long i = 1; i <= n; i++)cin >> a[i];for (long long i = 0; i <= n; i++)for (long long j = 0; j <= w; j++)dp[i][j] = -1e18;dp[0][0] = 0;//dp[i][j]選第i個材料時，此時正好j個材料的最大耐久度for (long long i = 1; i <= n; i++)for (long long j = 1; j <= w; j++)for (long long k = j - 1; k <= min(w, s + j - 1); k++)dp[i][j] = max(dp[i][j], dp[i-1][k] + a[i] * j);long long ans = -1e18;for (int i = 0; i <= w; i++)ans = max(ans, dp[n][i]);cout << ans << endl;return 0;
}

使用單調隊列優化后

在第三層的遍歷，求區間[j-1,min(w,j-1+s)]的最大值，可以使用單調隊列優化，降低時間復雜度。

//單調隊列優化
#include <iostream>
#include <deque>
using namespace std;
long long n, w, s;
long long a[5505];
long long dp[5505][5505];int main()
{cin >> n >> w >> s;for (long long i = 1; i <= n; i++)cin >> a[i];for (long long i = 0; i <= n; i++)for (long long j = 0; j <= w; j++)dp[i][j] = -1e18;dp[0][0] = 0;//dp[i][j]選第i個材料時，此時正好j個材料的最大耐久度for (long long i = 1; i <= n; i++){deque<long long> q;  //單調隊列，記錄區間最大值  存儲索引q.push_back(w);      //下面循環中w不會進隊列，需提前進隊列//[j-1,min(j-1+s,w)]//從右向左遍歷，因為左端點固定，而右端點使用了minfor (long long j = w; j >= 1; j--){//[j-1,min(j-1+s,w)]while (!q.empty() && q.front() > min(w, s + j - 1))q.pop_front();while (!q.empty() && dp[i - 1][q.back()] < dp[i - 1][j-1])q.pop_back();q.push_back(j-1); //比較的是q.back()和j-1位置//統計結果dp[i][j] = a[i] * j + dp[i - 1][q.front()];}}long long ans = -1e18;for (int i = 0; i <= w; i++)ans = max(ans, dp[n][i]);cout << ans << endl;return 0;
}

例題?

題目鏈接：1438. 絕對差不超過限制的最長連續子數組 - 力扣（LeetCode）?

?使用兩個單調隊列來維護窗口的最大值和最小值，結合遞增隊列和遞減隊列。當最大值減最小值超出給定的limit時，窗口的左邊界右移動，直到找到符合的位置，統計結果。

class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {//單調隊列，維護當前窗口的最大值和最小值deque<int> queMax,queMin;int n=nums.size();int left=0,right=0,ret=0;while(right<n){//維護隊列的單調性//遞減while(!queMax.empty()&&queMax.back()<nums[right])queMax.pop_back();//遞增while(!queMin.empty()&&queMin.back()>nums[right])queMin.pop_back();//入隊列元素queMin.push_back(nums[right]);queMax.push_back(nums[right]);while(!queMin.empty()&&!queMax.empty()&&queMax.front()-queMin.front()>limit){if(nums[left]==queMin.front())queMin.pop_front();if(nums[left]==queMax.front())queMax.pop_front();left++;}ret=max(ret,right-left+1);right++;}return ret;}
};