漫畫：滑動窗口系列 第一講（滑動窗口最大值）
- 2020 年 3 月 30 日
- 筆記
有讀者小夥伴建議講一下滑動窗口相關題型，因為經常面試會被問到。所以就開了這個系列（所以如果大家有想讓分享的題型都可以留言區告訴我，任何事情我覺得都需要有回饋。比如一個錯誤，你不回饋，我不知道..那就只能這樣過去了..）閑話不啰嗦，直接看題！
02
第239題：滑動窗口最大值
第239題：給定一個數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字。滑動窗口每次只向右移動一位。返回滑動窗口中的最大值。
給定一個數組 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
本題有一定難度！
建議認真閱讀
並課後練習~
02
題目分析
本題對於題目沒有太多需要額外說明的，應該都能理解，直接進行分析。我們很容易想到，可以通過遍歷所有的滑動窗口，找到每一個窗口的最大值，來進行暴力求解。那一共有多少個滑動窗口呢，小學題目，可以得到共有 L-k+1 個窗口。
假設 nums = [1,3,-1,-3,5,3,6,7]，和 k = 3，窗口數為6
根據分析，直接完成程式碼：
//java class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int len = nums.length; if (len * k == 0) return new int[0]; int [] win = new int[len - k + 1]; //遍歷所有的滑動窗口 for (int i = 0; i < len - k + 1; i++) { int max = Integer.MIN_VALUE; //找到每一個滑動窗口的最大值 for(int j = i; j < i + k; j++) { max = Math.max(max, nums[j]); } win[i] = max; } return win; } }
It's Bullshit！結果令我們很不滿意，時間複雜度達到了O(LK)，如果面試問到這道題，基本上只寫出這樣的程式碼，一定就掛掉了。那我們怎麼樣優化時間複雜度呢？有沒有可以O(L)的實現呢？=_=
03
線性題解
這裡不賣關子，其實這道題比較經典，我們可以採用隊列，DP，堆等方式進行求解，所有思路的主要源頭應該都是在窗口滑動的過程中，如何更快的完成查找最大值的過程。但是最典型的解法還是使用雙端隊列。具體怎麼來求解，一起看一下。
首先，我們了解一下，什麼是雙端隊列：是一種具有隊列和棧的性質的數據結構。雙端隊列中的元素可以從兩端彈出或者插入。
我們可以利用雙端隊列來實現一個窗口，目的是讓該窗口可以做到張弛有度（漢語博大精深，也就是長度動態變化。其實用游標或者其他解法的目的都是一樣的，就是去維護一個可變長的窗口）
然後我們再做一件事，只要遍歷該數組，同時在雙端隊列的頭去維護當前窗口的最大值（在遍歷過程中，發現當前元素比隊列中的元素大，就將原來隊列中的元素祭天），在整個遍歷的過程中我們再記錄下每一個窗口的最大值到結果數組中。最終結果數組就是我們想要的，整體圖解如下。
假設 nums = [1,3,-1,-3,5,3,6,7]，和 k = 3
（個人認為我畫的這個圖是目前全網對於雙端隊列本題解法比較清晰的一個…所以我覺得如果不點個贊的話…晤..）
根據分析，得出程式碼：
//go func maxSlidingWindow(nums []int, k int) []int { if len(nums) == 0 { return []int{} } //用切片模擬一個雙端隊列 queue := []int{} result := []int{} for i := range nums { for i > 0 && (len(queue) > 0) && nums[i] > queue[len(queue)-1] { //將比當前元素小的元素祭天 queue = queue[:len(queue)-1] } //將當前元素放入queue中 queue = append(queue, nums[i]) if i >= k && nums[i-k] == queue[0] { //維護隊列，保證其頭元素為當前窗口最大值 queue = queue[1:] } if i >= k-1 { //放入結果數組 result = append(result, queue[0]) } } return result }
Perfact~題目完成！看著一下子超越百分之99的用戶，是不是感覺很爽呢~
最後，記得打卡！
轉載是對我最大的支援~
註：本系列所有教程中都不會用到複雜的語言特性，大家不需要擔心沒有學過語法知識。演算法思想最重要，使用各語言純屬本人愛好。同時，本系列所有程式碼均在leetcode上進行過測試運行，保證其嚴謹性！
