0239. 滑動窗口最大值 · ttttt

# 0239. 滑動窗口最大值 ## 題目地址(239. 滑動窗口最大值) <https://leetcode-cn.com/problems/sliding-window-maximum/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個數組 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 提示： 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 1 <= k <= nums.length ``` ``` ## 前置知識 - 隊列 - 滑動窗口 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路符合直覺的想法是直接遍歷 nums, 然后然后用一個變量 slideWindow 去承載 k 個元素，然后對 slideWindow 求最大值，這是可以的，時間復雜度是 O(n \* k).代碼如下： JavaScript: ``` <pre class="calibre18">``` var maxSlidingWindow = function(nums, k) { // bad 時間復雜度O(n * k) if (nums.length === 0 || k === 0) return []; let slideWindow = []; const ret = []; for (let i = 0; i < nums.length - k + 1; i++) { for (let j = 0; j < k; j++) { slideWindow.push(nums[i + j]); } ret.push(Math.max(...slideWindow)); slideWindow = []; } return ret; }; ``` ``` Python3: ``` <pre class="calibre18">``` class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: if k == 0: return [] res = [] for r in range(k - 1, len(nums)): res.append(max(nums[r - k + 1:r + 1])) return res ``` ``` 但是如果真的是這樣，這道題也不會是 hard 吧？這道題有一個 follow up，要求你用線性的時間去完成。我們可以用雙端隊列來完成，思路是用一個雙端隊列來保存`接下來的滑動窗口可能成為最大值的數`。具體做法： - 入隊列 - 移除失效元素，失效元素有兩種 - 一種是已經超出窗口范圍了，比如我遍歷到第4個元素，k = 3，那么i = 0的元素就不應該出現在雙端隊列中了具體就是`索引大于 i - k + 1的元素都應該被清除` - 小于當前元素都沒有利用價值了，具體就是`從后往前遍歷（雙端隊列是一個遞減隊列）雙端隊列，如果小于當前元素就出隊列` 如果你仔細觀察的話，發現雙端隊列其實是一個遞減的一個隊列。因此隊首的元素一定是最大的。用圖來表示就是： ![](https://img.kancloud.cn/a7/96/a796fa22048df6449a98d94235ba689e_623x486.jpg) ## 關鍵點解析 - 雙端隊列簡化時間復雜度 - 滑動窗口 ## 代碼 JavaScript: ``` <pre class="calibre18">``` var maxSlidingWindow = function(nums, k) { // 雙端隊列優化時間復雜度, 時間復雜度O(n) const deque = []; // 存放在接下來的滑動窗口可能成為最大值的數 const ret = []; for (let i = 0; i < nums.length; i++) { // 清空失效元素 while (deque[0] 1) { deque.shift(); } while (nums[deque[deque.length - 1]] < nums[i]) { deque.pop(); } deque.push(i); if (i >= k - 1) { ret.push(nums[deque[0]]); } } return ret; }; ``` ``` Python3: ``` <pre class="calibre18">``` class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: deque, res, n = [], [], len(nums) for i in range(n): while deque and deque[0] 1: deque.pop(0) while deque and nums[i] > nums[deque[-1]]: deque.pop(-1) deque.append(i) if i >= k - 1: res.append(nums[deque[0]]) return res ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ## 擴展 ### 為什么用雙端隊列因為刪除無效元素的時候，會清除隊首的元素（索引太小了）或者隊尾(元素太小了)的元素。因此需要同時對隊首和隊尾進行操作，使用雙端隊列是一種合乎情理的做法。大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)