Problem: 239. 滑動窗口最大值
題目：給你一個整數數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字。滑動窗口每次只向右移動一位。返回滑動窗口中的最大值 。

【LeetCode 熱題 100】239. 滑動窗口最大值——（解法一）滑動窗口+暴力解

整體思路

這段代碼旨在高效地解決 “滑動窗口最大值” 問題。與上一個 O(N*k) 的暴力解法不同，此版本采用了 單調隊列（Monotonic Queue） 的核心思想，這是一種專門為此類問題設計的優化數據結構，能將時間復雜度降至線性級別。

算法的核心在于維護一個單調遞減的雙端隊列 win。這個隊列有以下幾個關鍵特性：

1. 存儲內容：隊列中存儲的不是元素值，而是元素在原數組 nums 中的 索引。
2. 單調性：隊列中的索引所對應的 nums 值是嚴格單調遞減的。即 nums[win[0]] > nums[win[1]] > nums[win[2]] ...。
3. 隊首即最大值：由于隊列的單調性，隊首元素 win.peekFirst() 始終是當前窗口內最大值的索引。

算法的執行步驟如下：

1. 初始化：

   • 創建一個結果數組 ans。
   • 創建一個雙端隊列 win 作為單調隊列。

2. 滑動窗口與單調隊列維護：

   • 算法使用 right 指針從左到右遍歷 nums 數組。對于每個新元素 nums[right]：
     a. 維護單調性（隊尾操作）：
     • 進入一個 while 循環，從隊尾開始檢查。如果隊尾索引對應的元素 nums[win.peekLast()] 小于或等于當前要入隊的新元素 nums[right]，則將隊尾元素彈出（win.pollLast()）。
     • 這個過程會持續進行，直到隊尾元素大于新元素，或者隊列為空。這確保了所有比新元素小的“舊”元素都被清除，因為它們在未來的窗口中不可能成為最大值。
     • 完成清理后，將當前元素的索引 right 加入隊尾（win.offerLast(right)）。
       b. 維護窗口大小（隊首操作）：
     • 檢查隊首元素的索引 win.peekFirst() 是否已經滑出當前窗口的左邊界。窗口的左邊界是 right - k + 1。如果隊首索引小于這個邊界（等價于 right - win.peekFirst() + 1 > k），說明隊首元素已過期，需要從隊首彈出（win.pollFirst()）。
       c. 記錄結果：
     • 當窗口形成后（right >= k - 1），根據單調隊列的性質，此時的隊首元素 win.peekFirst() 就是當前窗口最大值的索引。
     • 將 nums[win.peekFirst()] 存入結果數組 ans 的相應位置。

3. 返回結果：

   • 遍歷結束后，返回 ans 數組。

通過這種方式，每個元素最多入隊一次、出隊一次，使得在整個過程中找到所有窗口最大值的均攤時間復雜度為 O(1)，從而實現了整體的線性時間復雜度。

完整代碼

class Solution {/*** 計算滑動窗口的最大值（優化版）。* @param nums 整數數組* @param k 窗口大小* @return 包含每個窗口最大值的數組*/public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;// 計算結果數組的長度int m = n - k + 1;int[] ans = new int[m];// win: 一個雙端隊列，用作單調隊列，存儲元素的索引。// 隊列中的索引對應的 nums 值保持單調遞減。Deque<Integer> win = new ArrayDeque<>();// right 指針作為窗口的右邊界，遍歷整個數組for (int right = 0; right < n; right++) {// 步驟 1: 維護隊列的單調遞減性// 當隊列不為空，且隊尾索引對應的元素小于或等于當前元素時，// 將隊尾元素彈出。因為這個較小的元素在未來不可能成為最大值。while (!win.isEmpty() && nums[win.peekLast()] <= nums[right]) {win.pollLast();}// 將當前元素的索引加入隊尾win.offerLast(right);// 步驟 2: 維護窗口的有效范圍// 檢查隊首元素的索引是否已經滑出窗口左邊界。// 窗口的左邊界是 right - k + 1。如果隊首索引小于它，則說明已過期。// (right - win.peekFirst() + 1) 是隊首元素和當前元素構成的窗口大小。if (right - win.peekFirst() + 1 > k) {// 彈出過期的隊首元素win.pollFirst();}// 步驟 3: 記錄結果// 當窗口大小達到 k 時（即 right 遍歷到第 k-1 個元素時），開始記錄最大值if (right >= k - 1) {// 由于隊列的單調性，隊首元素始終是當前窗口內最大值的索引ans[right - k + 1] = nums[win.peekFirst()];}}return ans;}
}

時空復雜度

時間復雜度：O(N)

1. 循環：代碼的主體是一個 for 循環，它遍歷 nums 數組一次，執行 N 次。
2. 隊列操作：
   • while 循環中的 win.pollLast() 和 if 判斷中的 win.pollFirst() 操作看起來可能導致時間復雜度升高。
   • 然而，每個元素的索引最多只會入隊一次和出隊一次。
   • offerLast 將每個索引 0 到 N-1 各壓入一次，總共 N 次。
   • pollLast 和 pollFirst 共同將這些索引彈出，每個索引最多被彈出一次。
   • 因此，所有隊列操作的總次數是 O(N) 級別的。將這些操作的成本均攤到 N 次外層循環中，每次循環的均攤時間復雜度為 O(1)。

綜合分析：
算法由 N 次均攤時間復雜度為 O(1) 的操作組成。因此，總的時間復雜度是 O(N)。

空間復雜度：O(k)

1. 主要存儲開銷：算法使用了一個雙端隊列 win 來存儲索引。
2. 空間大小：隊列 win 中存儲的是當前有效窗口內的候選最大值的索引。在任何時刻，隊列的長度都不會超過窗口大小 k。例如，如果輸入數組是嚴格遞減的，如 [5, 4, 3, 2, 1] 且 k=3，隊列會存儲 [i, i+1, i+2] 三個索引。因此，隊列的最大空間占用為 O(k)。
3. 結果數組：ans 數組的空間為 O(N)，但不計入額外輔助空間。

綜合分析：
算法所需的額外輔助空間主要由單調隊列 win 決定，其大小與窗口大小 k 成正比。因此，空間復雜度為 O(k)。

【LeetCode 熱題 100】239. 滑動窗口最大值——（解法三）滑動窗口+單調隊列+數組