詳解滑動窗口最值問題
滑動問題包含一個滑動窗口，它是一個運行在一個大數組上的子列表，該數組是一個底層元素集合。一般用來求最值問題。
LeetCode 第 239 題：滑動窗口最大值
題目來源于 LeetCode 上第 239 號問題：滑動窗口最大值。題目難度為 Hard 。
給定一個數組 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
看到這個題之后，第一直覺就是暴力解法，用兩層循環依次查詢滑動窗口的最大值，實現代碼如下。
- nums = [1, 3, -1, -3, 5, 3, 6, 7]
- k = 3
- res = []
- for i in range(k, len(nums) + 1):
- res.append(max(nums[i - k:i]))
- print(res) #[3, 3, 5, 5, 6, 7]
但max執行效率卻很低，在Leetcode上不能通過，因此我們需要繼續找尋新的解決方案。
雙端隊列
Deque 的含義是 “double ended queue”，即雙端隊列，它具有隊列和棧的性質的數據結構。顧名思義，它是一種前端與后端都支持插入和刪除操作的隊列。
在Python中，我直接使用列表代替雙端隊列，pop(0)表示前端刪除操作，pop()表示后端刪除操作。
雙端隊列window記錄滑動窗口中元素的索引，隊列左邊界記錄當前滑動窗口中最大元素的索引
- 當隊列非空，左邊界出界時(滑動窗口向右移導致的)，更新左邊界
- 當隊列非空，將隊列中索引對應的元素值比 num 小的移除，更新隊列
- 當索引 i 大于 k-1，更新輸出結果
- class Solution:
- def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
- if not nums: return []
- window ,res = [],[]
- for i,x in enumerate(nums):
- # 如果存在窗口 而且窗口的第一個數 不在這個范圍，就出去
- if i >= k and window[0] <= i-k:
- window.pop(0)
- # 每次進入窗口的和最后一個比較，如果大了，最后一個直接刪除
- while window and nums[window[-1]] <= x:
- window.pop()
- # 無論是不是刪除最后一個，都要加入x到窗口中
- window.append(i)
- # 如果出了窗口，就把窗口的頭加入到res中
- if i >= k-1:
- res.append(nums[window[0]])
- return res
LeetCode 第 3 題 無重復字符的最長子串
給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。
- # 示例 1:
- # 輸入: "abcabcbb"
- # 輸出: 3
- #解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。
- # 示例 2:
- # 輸入: "bbbbb"
- #輸出: 1
- #解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。
- # 示例 3
- # 輸入: "pwwkew"
- #輸出: 3
- #解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。
- #請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
下面我們看看，“滑動窗口”如何進行字符串處理。結合題目中的例子“abcabcbb”這個字符串，我們來看看如何找它的無重復最長子串。
首先，我們定義窗口的兩端：begin和end，分別表示要找的子串的開頭和結尾。
開始的時候，begin和end都指向0的位置即‘a’，然后end不斷后移(窗口變寬)，當遇到第二個‘a’時(遇見重復字符)就得到一個子串，其長度就是end和begin位置的差。
如何判斷是否遇到了重復字符‘a’呢?需要一個字典作為輔助數據結構，把end從頭開始遇到的每個字符及其索引位置都放到字典里面，end每次移動到新字符就查一下字典即可
- class Solution:
- def lengthOfLongestSubstring(self, s: str) -> int:
- # 定義兩個變量res和start,res用于存儲最長子字符串的長度，start存儲無重復子串左邊的起始位置。
- '''
- 然后創建一個哈希表，遍歷整個字符串，如果字符串沒有在哈希表中出現，說明沒有遇到過該字符，則此時計算最長無重復子串，當哈希表中的值小于left，說明left位置更新了，需要重新計算最長無重復子串。每次在哈希表中將當前字符串對應的賦值加1。
- :param s:
- :return:
- '''
- d, res, start = {}, 0, 0
- for i, ch in enumerate(s):
- if ch in d:
- start = max(start, d[ch] + 1)
- res = max(res, i - start + 1)
- d[ch] = i
- return res
人生最重要的不是所站的位置，而是內心所朝的方向。只要我在每篇博文中寫得自己體會，修煉身心;在每天的不斷重復學習中，耐住寂寞，練就真功，不畏艱難，奮勇前行，不忘初心，砥礪前行，人生定會有所收獲，不留遺憾 (作者：Runsen )
本文已收錄 GitHub https://github.com/MaoliRUNsen/runsenlearnpy100
