在上一篇文章中，我們介紹了「單調棧」這一最常考察的線性數據結構。而今天我們将繼續沿着這個思路，介紹另一個與其 「齊名」的線性數據結構，即「單調隊列」。

「單調隊列」在「數據結構」題中的分布較為廣泛，且常被當作優化「動态規劃」的一種重要手段，因此該算法在面試中考察的頻率較高，屬于必知必會的知識點。

首先我們來回憶一下「隊列」。「隊列」是一種「先進先出」的線性數據結構，其中元素隻能從隊尾進，從隊首出。

如下圖所示，3 1 4 5 2 7 依次入隊又依次出隊，其結果滿足「先進先出」的要求。另外，有标記的位置分别代表隊首與隊尾，其中左邊為隊首。

回憶完「隊列」後，我們開始「單調隊列」的講解。

什麼是「單調隊列」？顧名思義，「單調隊列」就是隊列内元素滿足單調性的隊列結構。且為了滿足隊列内元素的單調性，隊尾也可彈出元素。此處的單調性分為單調遞增與單調遞減，為了便于描述，接下來以「單調遞增隊列」為例進行講解。

「單調遞增隊列」中「隊尾」的操作與「單調遞增棧」中「棧頂」的操作一緻，即假設當前元素為 x，若隊尾元素 <= x，則将 x 入隊，否則不斷彈出隊尾元素，直至隊尾元素 <= x。

例如以 3 1 4 5 2 7 為例，若「隊首」始終不彈出元素，則其具體過程如下圖所示。

由此可知，「單調隊列」與「單調棧」的最大區别就在于「隊首」的操作，「何時将隊首元素出隊」是「單調隊列」算法的關鍵。

然而「隊首」的操作往往具有多樣性，并非一成不變，因此接下來我們以三道經典題型為例來進一步講解該算法。

239. 滑動窗口最大值

給你一個整數數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你隻可以看到在滑動窗口内的 k 個數字。滑動窗口每次隻向右移動一位。

返回滑動窗口中的最大值。

輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3 輸出：[3,3,5,5,6,7] 解釋： 滑動窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

輸入：nums = [1], k = 1 輸出：[1]

輸入：nums = [1,-1], k = 1 輸出：[1,-1]

輸入：nums = [9,11], k = 2 輸出：[11]

輸入：nums = [4,-2], k = 2 輸出：[4]

• 1 <= nums.length <= 1e5
• -1e4 <= nums[i] <= 1e4
• 1 <= k <= nums.length

「滑動窗口中的最大 / 小值」是「單調隊列」最為經典的應用，其它「單調隊列」的題型大多從該模型演變而來，因此大家需要着重理解此題。

由于本題求的是「滑動窗口中的最大值」，因此我們使用「單調遞減隊列來進行解決」。另外由于窗口大小為 k，所以當窗口右端點下标為 r 時，影響當前窗口最大值的元素下标範圍為 [r-k 1, r]。

由此我們可以制定「隊首」彈出元素的規則，即當「隊尾元素的下标 - 隊首元素的下标 1」大于 k 時，彈出「隊首」元素。

接下來我們以 nums = [3 2 1 -1 2]、k = 3 為例，展示「單調遞減隊列」的具體執行過程。且為了便于展示，我們在「單調隊列」中存儲的是元素的下标，而不是元素的數值。

觀察上述執行過程，我們可以發現元素入隊分為兩步，第一步是「不斷彈出隊尾元素」直至隊尾元素代表的數值大于等于當前元素，第二步是「彈出隊首元素」直至「當前元素下标 - 隊首元素下标 1」小于等于 k。

進一步觀察可以發現，當前元素入隊的兩步操作結束後，以當前元素為右端點的窗口，其窗口最大值為「隊首元素」所對應的數值。

我們以當前元素為第四個元素（即 -1）為例來幫助大家理解。

此時隊尾數值為 nums[3] = 1，即隊尾數值大于等于當前元素，因此當前元素入隊（隊列中存儲元素下标），如下圖所示。

入隊後「彈出隊首元素」直至「當前元素下标 - 隊首元素下标 1」小于等于 k，因此隊首元素被彈出，最終狀态如下圖所示。

第四個元素完成上述兩步入隊操作後，隊首元素下标為 2，其對應的數值 nums[2] = 2，當前窗口最大值 max([2 1 -1]) = 2。因此印證了剛才的結論，即當前元素入隊的兩步操作結束後，以當前元素為右端點的窗口，其窗口最大值為「隊首元素」所對應的數值。

由此我們可以發現「單調隊列」的核心功能為「求出數組中每一個元素其固定區間範圍内的最大 / 小值」。并且由于每個元素出隊、入隊最多一次，因此總的時間複雜度為 O(n)。

根據上述算法即可解決本題，具體實現細節見下述代碼。

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { int len = nums.size(), l = 0, r = -1; vector<int> q(len, 0), ans; for (int i = 0; i < len; i ) { while (l <= r && nums[q[r]] < nums[i]) r--; q[ r] = i; if (i-q[l] 1 > k) l ; if (i >= k-1) ans.push_back(nums[q[l]]); } return ans; } }；

1425. 帶限制的子序列和

給你一個整數數組 nums 和一個整數 k ，請你返回「非空」子序列元素和的最大值，子序列需要滿足：子序列中每兩個「相鄰」的整數 nums[i] 和 nums[j]，它們在原數組中的下标 i 和 j 滿足 i < j 且 j - i <= k 。

數組的子序列定義為：将數組中的若幹個數字删除（可以删除 0 個數字），剩下的數字按照原本的順序排布。

輸入：nums = [10,2,-10,5,20], k = 2 輸出：37 解釋：子序列為 [10, 2, 5, 20] 。

輸入：nums = [-1,-2,-3], k = 1 輸出：-1 解釋：子序列必須是非空的，所以我們選擇最大的數字。

輸入：nums = [10,-2,-10,-5,20], k = 2 輸出：23 解釋：子序列為 [10, -2, -5, 20] 。

• 1 <= k <= nums.length <= 1e5

• -1e4 <= nums[i] <= 1e4

本題求解的是最大「非空」子序列元素和，且相鄰兩個元素坐标差小于等于 k。由于題目的主體是子序列，因此我們采取一種「增量式」的思想來進一步思考。

假設當前有一個子序列 A，現在想在 A 後面再添加一個元素 x，則我們隻需要考慮 x 和 A 中最後一個元素的坐标差是否小于等于 k，而不用考慮 A 中的所有元素。更明确地說，對于子序列 A，我們隻需要記錄它的元素和與最後一個元素的下标即可。

基于上述的思考，不難想到使用動态規劃的算法，令 f[i] 表示以 nums[i] 為子序列最後一個元素時的最大元素和，則可以得到如下遞推公式：

根據上述公式，我們可以得到一種暴力的做法，即對于每一個 i，向前枚舉合法的 j 來更新 f[i]，時間複雜度為 O(nk)。

觀察題目中的數據範圍，暴力做法很明顯無法通過，因此我們考慮如何優化。

f[i] 由前面 k 個數中的最大值轉移而來，因此不難想到使用「單調隊列」算法來進行優化。用「單調隊列」來維護 f 數組中大小為 k 的窗口的最大值即可完成此題，時間複雜度優化至 O(n)，具體細節見代碼。

通過此題，我們可以更深刻地意識到，「單調隊列」在求取「數組中每一個元素其固定區間範圍内的最大 / 小值」的作用。而也正是該功能，使得「單調隊列」常作為「動态規劃」的一種優化手段出現在面試題中。

class Solution { public: int constrainedSubsetSum(vector<int>& nums, int k) { int len = nums.size(), l = 0, r = -1, ans = nums[0]; vector<int> q(len, 0); for (int i = 0; i < len; i ) { if (l <= r && i - q[l] > k) l ; if (l <= r) nums[i] = max(nums[i], nums[i] nums[q[l]]); ans = max(ans, nums[i]); while (l <= r && nums[q[r]] < nums[i]) r--; q[ r] = i; } return ans; } };

862. 和至少為 K 的最短子數組

返回 A 的最短的非空連續子數組的長度，該子數組的和至少為 K 。

如果沒有和至少為 K 的非空子數組，返回 -1。

輸入：A = [1], K = 1 輸出：1

輸入：A = [1,2], K = 4 輸出：-1

輸入：A = [2,-1,2], K = 3 輸出：3

• 1 <= A.length <= 50000
• -1e5 <= A[i] <= 1e5
• 1 <= K <= 1e9

本題求解的是元素和大于等于 K 的最短非空連續子數組，由于涉及連續子數組和的求取，所以先對 A 做一個前綴和。

令 B 為 A 的前綴和數組，即 A 在 [x, y] 區間的元素和等于 B[y] - B[x-1]。又因為我們需要求解元素和大于等于 K 的最短連續子數組，即對于 B[y] 來說，找到最大的 x 滿足 0 <= x < y 且 B[y] - B[x] >= K，也就是說，我們既希望 B[x] 小又希望 x 大。

基于上述觀察，我們可以維護一個單調遞增隊列 [x1, x2, ..., xp] 存儲所有可能更新答案的下标 x（左邊為隊首）。隊列滿足從左至右，下标遞增且下标對應的 B 中元素值也遞增。

假設當前元素為 B[y]，若 B[xp] > B[y] 則彈出，因為 y 比 xp 更大且 B[y] 比 B[xp] 更小，即 y 一定比 xp 更優。基于該策略不斷彈出隊尾元素，直至條件不再滿足。

對于隊首元素來說，若 B[y] - B[x1] >= K，則彈出 x1 并更新答案 ans = min(ans, y - x1)。因為 y 是不斷變大的，就算之後存在 y' > y 滿足 B[y'] - B[x1] >= K，y 距 x1 仍近于 y'，因此可以直接将 x1 彈出而不影響答案。基于該策略不斷彈出隊首元素，直至條件不再滿足。

另外，上述算法未考慮到區間 [1, y] 的情況，因此若 B[y] >= K，則更新答案 ans = min(ans, y)。

觀察上述算法，可以發現隊尾操作與基礎題「滑動窗口」沒有區别，主要變化在于「隊首彈出元素」的條件，而本題也正是通過對該條件的修改使得題目思維難度變大。

class Solution { public: int shortestSubarray(vector<int>& A, int K) { int len = A.size(), l = 0, r = -1, ans = len 1; vector<int> q(len, 0); for (int i = 1; i < len; i ) A[i] = A[i-1]; for (int i = 0; i < len; i ) { while (l <= r && A[q[r]] > A[i]) r--; q[ r] = i; while (A[q[r]]-A[q[l]] >= K) { ans = min(ans, q[r]-q[l]); l ; } if (A[i] >= K) ans = min(ans, i 1); } if (ans == len 1) ans = -1; return ans; } };

通過上述三道例題的講解，希望大家對于「單調隊列」有了更多的了解，其實「單調隊列」就是在「單調棧」的基礎上加了一個「彈出隊首」的操作，雖然該操作的添加極大地增加了該算法的多樣性。

不過作為初學者，大家隻需要理解「單調隊列」在「滑動窗口」問題上的應用即可，即在 O(n) 時間複雜度内求出數組中每一個元素其固定區間範圍的最大 / 小值。

至此我們完成了兩大基礎線性數據結構的講解（單調棧與單調隊列），這兩個數據結構的變化較多，大家需要在日後刷題的過程中進一步地感受與體會。

本文作者：Gene_Liu

聲明：本文歸 “力扣” 版權所有，如需轉載請聯系。文中部分圖片來源于網絡，如有侵權聯系删除。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!