這段文字描述的是使用單調隊列（Monotonic Queue） 解決滑動窗口最大值問題的優化算法。我來簡單解釋一下：
核心思路
-
問題分析：在滑動窗口中，若存在兩個下標
i < j且nums[i] ≤ nums[j]，則nums[i]永遠不可能成為后續窗口的最大值（因為j會比i更晚離開窗口）。因此，可以提前淘汰nums[i]。 -
數據結構選擇：使用雙端隊列（Deque）維護一個單調遞減的下標序列，確保隊列中元素對應的值從隊首到隊尾嚴格遞減。
-
維護單調隊列：
- 插入新元素：將新元素與隊尾比較，若新元素更大，則不斷彈出隊尾，直到滿足單調性。
- 淘汰舊元素：檢查隊首元素是否已超出窗口范圍，若超出則彈出隊首。
算法步驟
- 初始化隊列：遍歷前
k個元素，維護單調隊列。 - 處理每個窗口：
- 淘汰舊元素：若隊首下標超出窗口左邊界，彈出隊首。
- 插入新元素：將當前元素下標加入隊尾，彈出所有不大于當前值的隊尾元素。
- 記錄最大值：隊首元素對應的值即為當前窗口的最大值。
- 滑動窗口：重復步驟2，直到處理完所有窗口。
示例代碼（C++）
#include <iostream>
#include <vector>
#include <deque>
using namespace std;vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();vector<int> result;if (n == 0 || k == 0) return result;deque<int> q; // 存儲下標，對應的值單調遞減// 初始化第一個窗口（前k個元素）for (int i = 0; i < k; ++i) {// 彈出所有比當前元素小的隊尾下標（維護單調遞減）while (!q.empty() && nums[i] >= nums[q.back()]) {q.pop_back();}q.push_back(i);}result.push_back(nums[q.front()]); // 第一個窗口的最大值// 滑動窗口處理后續元素for (int i = k; i < n; ++i) {// 淘汰已離開窗口的隊首下標（左邊界為i-k+1，下標<=i-k時淘汰）while (!q.empty() && q.front() <= i - k) {q.pop_front();}// 維護單調遞減：彈出所有比當前元素小的隊尾下標while (!q.empty() && nums[i] >= nums[q.back()]) {q.pop_back();}q.push_back(i);result.push_back(nums[q.front()]); // 當前窗口最大值}return result;
}// 測試示例
int main() {vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};int k = 3;vector<int> res = maxSlidingWindow(nums, k);cout << "滑動窗口最大值：";for (int num : res) {cout << num << " ";}// 輸出：3 3 5 5 6 7return 0;
}
可將步驟整合在一個循環里：
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();if (n == 0 || k == 0) {return {};}deque<int> q; // 雙端隊列，存儲窗口內元素的索引vector<int> res;for (int i = 0; i < n; ++i) {// 移除隊列中不在當前窗口內的元素while (!q.empty() && q.front() <= i - k) {q.pop_front();}// 移除隊列中所有小于等于當前元素的索引while (!q.empty() && nums[i] >= nums[q.back()]) {q.pop_back();}// 將當前元素的索引加入隊列q.push_back(i);// 當窗口形成后，記錄當前窗口的最大值if (i >= k - 1) {res.push_back(nums[q.front()]);}}return res;}
};復雜度分析
- 時間復雜度：O(n)，每個元素最多入隊和出隊一次。
- 空間復雜度：O(k)，隊列中最多存儲
k個元素。
關鍵點
- 單調隊列：通過維護單調性，避免重復比較，將暴力算法的 O(nk) 優化到 O(n)。
- 雙端隊列：支持 O(1) 時間復雜度的隊首和隊尾操作。
- 應用場景：適用于求解滑動窗口最大值/最小值、子數組最大和等問題。
