前言科普：什么是滑動窗口算法
滑動問題包含一個滑動窗口，它是一個運行在一個大數組上的子列表，該數組是一個底層元素集合。
假設有數組 [a b c d e f g h ]，一個大小為 3 的 滑動窗口 在其上滑動，則有：
[a b c] [b c d] [c d e] [d e f] [e f g] [f g h]
一般情況下就是使用這個窗口在數組的 合法區間 內進行滑動，同時 動態地 記錄一些有用的數據，很多情況下，能夠極大地提高算法地效率。
1. 滑動窗口最大值
題目來源于 LeetCode 上第 239 號問題：滑動窗口最大值。題目難度為 Hard，目前通過率為 40.5% 。
題目描述
給定一個數組 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
題目解析
利用一個 雙端隊列，在隊列中存儲元素在數組中的位置， 并且維持隊列的嚴格遞減,，也就說維持隊首元素是 最大的 ，當遍歷到一個新元素時, 如果隊列里有比當前元素小的，就將其移除隊列，以保證隊列的遞減。當隊列元素位置之差大于 k，就將隊首元素移除。
補充：什么是雙端隊列（Dqueue）
Deque 的含義是 “double ended queue”，即雙端隊列，它具有隊列和棧的性質的數據結構。顧名思義，它是一種前端與后端都支持插入和刪除操作的隊列。
Deque 繼承自 Queue（隊列），它的直接實現有 ArrayDeque、LinkedList 等。
動畫描述
代碼實現
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { //有點坑，題目里都說了數組不為空，且 k > 0。但是看了一下，測試用例里面還是有nums = [], k = 0，所以只好加上這個判斷 if (nums == null || nums.length < k || k == 0) return new int[0]; int[] res = new int[nums.length - k + 1]; //雙端隊列 Deque<Integer> deque = new LinkedList<>(); for (int i = 0; i < nums.length; i++) { //在尾部添加元素，并保證左邊元素都比尾部大 while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) { deque.removeLast(); } deque.addLast(i); //在頭部移除元素 if (deque.getFirst() == i - k) { deque.removeFirst(); } //輸出結果 if (i >= k - 1) { res[i - k + 1] = nums[deque.getFirst()]; } } return res; }}2. 無重復字符的最長子串
題目來源于 LeetCode 上第 3 號問題：無重復字符的最長子串。題目難度為 Medium，目前通過率為 29.0% 。
題目描述
給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。
題目解析
建立一個256位大小的整型數組 freg ，用來建立字符和其出現位置之間的映射。
維護一個滑動窗口，窗口內的都是沒有重復的字符，去盡可能的擴大窗口的大小，窗口不停的向右滑動。
（1）如果當前遍歷到的字符從未出現過，那么直接擴大右邊界；
（2）如果當前遍歷到的字符出現過，則縮小窗口（左邊索引向右移動），然后繼續觀察當前遍歷到的字符；
（3）重復（1）（2），直到左邊索引無法再移動；
（4）維護一個結果res，每次用出現過的窗口大小來更新結果 res，最后返回 res 獲取結果。
動畫描述
代碼實現
// 滑動窗口// 時間復雜度: O(len(s))// 空間復雜度: O(len(charset))class Solution {public: int lengthOfLongestSubstring(string s) { int freq[256] = {0}; int l = 0, r = -1; //滑動窗口為s[l...r] int res = 0; // 整個循環從 l == 0; r == -1 這個空窗口開始 // 到l == s.size(); r == s.size()-1 這個空窗口截止 // 在每次循環里逐漸改變窗口, 維護freq, 并記錄當前窗口中是否找到了一個新的最優值 while(l < s.size()){ if(r + 1 < s.size() && freq[s[r+1]] == 0){ r++; freq[s[r]]++; }else { //r已經到頭 || freq[s[r+1]] == 1 freq[s[l]]--; l++; } res = max(res, r-l+1); } return res; }};3. 存在重復元素 II
題目來源于 LeetCode 上第 219 號問題：存在重復元素 II。題目難度為 Easy，目前通過率為 33.9% 。
題目描述
給定一個整數數組和一個整數 k，判斷數組中是否存在兩個不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的絕對值最大為 k。
示例 1:
輸入: nums = [1,2,3,1], k = 3
輸出: true
示例 2:
輸入: nums = [1,0,1,1], k = 1
輸出: true
示例 3:
輸入: nums = [1,2,3,1,2,3], k = 2
輸出: false
題目解析
使用用滑動窗口與查找表來解決。
代碼實現
// 時間復雜度: O(n)// 空間復雜度: O(k)class Solution {public: bool containsNearbyDuplicate(vector<int>& nums, int k) { if(nums.size() <= 1) return false; if(k <= 0) return false; unordered_set<int> record; for(int i = 0 ; i < nums.size() ; i ++){ if(record.find(nums[i]) != record.end()){ return true; } record.insert(nums[i]); // 保持record中最多有k個元素 // 因為在下一次循環中會添加一個新元素,使得總共考慮k+1個元素 if(record.size() == k + 1){ record.erase(nums[i - k]); } } return false; }};4. 長度最小的子數組
題目來源于 LeetCode 上第 209 號問題：長度最小的子數組。題目難度為 Medium，目前通過率為 37.7% 。
題目描述
給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的連續子數組。如果不存在符合條件的連續子數組，返回 0。
示例:
輸入: s = 7, nums = [2,3,1,2,4,3]
輸出: 2
解釋: 子數組 [4,3] 是該條件下的長度最小的連續子數組。
題目解析
定義兩個指針 left 和 right ，分別記錄子數組的左右的邊界位置。
（1）讓 right 向右移，直到子數組和大于等于給定值或者 right 達到數組末尾；
（2）更新最短距離，將 left 像右移一位, sum 減去移去的值；
（3）重復（1）（2）步驟，直到 right 到達末尾，且 left 到達臨界位置
動畫描述
設置滑動窗口的長度為 0 ，位于數軸的最左端。
1 .滑動窗口右端 R 開始移動，直到區間滿足給定的條件，也就是和大于 7 ，此時停止于第三個元素 2，當前的最優長度為 4
圖 1
2. 滑動窗口左端 L 開始移動，縮小滑動窗口的大小，停止于第一個元素 3，此時區間和為 6，使得區間和不滿足給定的條件（此時不大于 7）
圖片 2
3. 滑動窗口右端 R 繼續移動，停止于第四個元素 4，此時和位 10 ，但最優長度仍然為 4
圖片 3
代碼實現
// 滑動窗口的思路// 時間復雜度: O(n)// 空間復雜度: O(1)class Solution { public int minSubArrayLen(int s, int[] nums) { int l= 0,r = -1; // nums[l...r]為我們的滑動窗口 int sum = 0; int result = nums.length + 1; while (l < nums.length){ // 窗口的左邊界在數組范圍內,則循環繼續 if( r+1 <nums.length && sum < s){ r++; sum += nums[r]; }else { // r已經到頭 或者 sum >= s sum -= nums[l]; l++; } if(sum >= s){ result = (r-l+1) < result ? (r-l+1) : result ; } } if(result==nums.length+1){ return 0; } return result; }}總結
以上所述是小編給大家介紹的分享幾道和「滑動窗口」有關的算法面試題,希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對武林網網站的支持！
如果你覺得本文對你有幫助，歡迎轉載，煩請注明出處，謝謝！
新聞熱點
疑難解答
