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

整體思路

這段代碼的目的是解決經典的 “滑動窗口最大值” 問題。即，在一個整數數組 nums 中，找出一個大小為 k 的滑動窗口在從左到右移動時，每個窗口內的最大值。

該算法實現了一種 模擬滑動窗口 的暴力解法。它雖然使用了雙端隊列（Deque）這一數據結構，但并沒有發揮其在最優解法（單調隊列）中的關鍵作用，而是僅僅將其用作一個普通的隊列來存儲當前窗口內的所有元素。

其核心邏輯步驟如下：

1. 初始化：

   • 創建一個結果數組 ans，其長度為 n - k + 1，因為這正是滑動窗口的總數。
   • 創建一個雙端隊列 win，用來存儲當前滑動窗口中的所有元素。

2. 滑動窗口模擬：

   • 算法使用一個 for 循環，由 right 指針驅動，從左到右遍歷整個 nums 數組。right 代表窗口的右邊界。
   • 窗口維護：
     a. 元素出隊（收縮窗口）：當窗口已經形成并需要向右滑動時（即 right > k - 1，意味著要加入第 k+1 個元素了），就從隊列的頭部彈出一個元素（win.pop()）。這模擬了窗口最左邊的元素移出窗口的過程。
     b. 元素入隊（擴張窗口）：將當前 right 指針指向的元素 nums[right] 加入到隊列的尾部（win.add())。
   • 通過這兩步，win 隊列始終保持著當前滑動窗口內的所有元素。

3. 查找當前窗口最大值（暴力法）：

   • 【效率瓶頸】 在每次更新窗口后，代碼會進入一個內部的 for-each 循環，遍歷 win 隊列中的 所有元素，以線性掃描的方式找出當前窗口的最大值 max。
   • 這是該算法效率不高的根本原因。

4. 記錄結果：

   • 當窗口首次形成（即 right >= k - 1）以及后續的每次滑動后，將上一步找到的最大值 max 存入結果數組 ans 的相應位置（ans[right - k + 1]）。

5. 返回結果：

   • 遍歷結束后，返回填充好的 ans 數組。

總結來說，這是一個思路直接、易于理解的解法：用隊列維護窗口元素，每次滑動后，重新掃描整個窗口找到最大值。

完整代碼

class Solution {/*** 計算滑動窗口的最大值。* @param nums 整數數組* @param k 窗口大小* @return 包含每個窗口最大值的數組*/public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;// 計算結果數組的長度，即滑動窗口的總數int m = n - k + 1;// ans 用于存儲每個窗口的最大值int[] ans = new int[m];// win 是一個雙端隊列，在此實現中被用作普通隊列來存儲當前窗口的所有元素Deque<Integer> win = new ArrayDeque<>(k); // 初始化容量為k// right 指針作為窗口的右邊界，遍歷整個數組for (int right = 0; right < n; right++) {// 當窗口大小即將超過 k 時，需要從左側移除一個元素// right > k - 1 意味著我們正要處理第 k+1 個元素（從0計數），此時窗口已滿if (right > k - 1) {// win.pop() 從隊列頭部移除元素，模擬窗口向右滑動win.pop();}// 將當前 right 指針指向的元素加入隊列尾部win.add(nums[right]);// 【效率瓶頸】// 在每次窗口更新后，暴力遍歷當前窗口中的所有元素以查找最大值int max = Integer.MIN_VALUE;for (int x : win) {// 使用三元運算符更新最大值max = max > x ? max : x;}// 當窗口大小達到 k 時，開始記錄結果// right >= k - 1 標志著第一個完整的窗口已經形成if (right >= k - 1) {// 計算當前窗口在結果數組 ans 中的索引ans[right - k + 1] = max;}}return ans;}
}

時空復雜度

時間復雜度：O(N * k)

1. 外層循環：for (int right = 0; right < n; right++) 遍歷整個輸入數組 nums，執行 N 次，其中 N 是 nums 的長度。
2. 內層循環：for (int x : win) 循環遍歷 win 隊列中的所有元素。win 隊列的大小始終保持在 k 或小于 k。在窗口形成后，其大小恒為 k。因此，這個內層循環每次執行的操作數是 O(k)。
3. 循環內部操作：隊列的 pop() 和 add() 操作的平均時間復雜度都是 O(1)。

綜合分析：
算法的總時間復雜度由外層循環和內層循環的乘積決定。外層循環執行 N 次，每次內部都進行一次 O(k) 的掃描。因此，總的時間復雜度為 N * O(k) = O(N * k)。

空間復雜度：O(k)

1. 主要存儲開銷：算法使用了一個雙端隊列 win 來存儲窗口內的元素。
2. 空間大小：win 隊列的大小最多為 k，因為它存儲的是一個大小為 k 的滑動窗口的元素。
3. 結果數組：ans 數組的大小是 N - k + 1，屬于 O(N) 級別。在復雜度分析中，輸出結果所占用的空間通常不計入 額外輔助空間（auxiliary space）。

綜合分析：
算法所需的額外輔助空間主要由 win 隊列決定。因此，其空間復雜度為 O(k)。如果把輸出數組也計算在內，則總空間為 O(N)。按照標準，我們通常只分析輔助空間，即 O(k)。

注意：暴力解會超時

這個方法時間復雜度為O(N * k)，會超時。

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

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