[[373481]]

 滑動(dòng)問題包含一個(gè)滑動(dòng)窗口，它是一個(gè)運(yùn)行在一個(gè)大數(shù)組上的子列表，該數(shù)組是一個(gè)底層元素集合。一般用來求最值問題。

LeetCode 第 239 題：滑動(dòng)窗口最大值

題目來源于 LeetCode 上第 239 號問題：滑動(dòng)窗口最大值。題目難度為 Hard 。

給定一個(gè)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 
輸出: [3,3,5,5,6,7]  
解釋:  
 
  滑動(dòng)窗口的位置                最大值 
---------------                ----- 
[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 

看到這個(gè)題之后，第一直覺就是暴力解法，用兩層循環(huán)依次查詢滑動(dòng)窗口的最大值，實(shí)現(xiàn)代碼如下。

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執(zhí)行效率卻很低，在Leetcode上不能通過，因此我們需要繼續(xù)找尋新的解決方案。

雙端隊(duì)列

Deque 的含義是 “double ended queue”，即雙端隊(duì)列，它具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。顧名思義，它是一種前端與后端都支持插入和刪除操作的隊(duì)列。

在Python中，我直接使用列表代替雙端隊(duì)列，pop(0)表示前端刪除操作，pop()表示后端刪除操作。

雙端隊(duì)列window記錄滑動(dòng)窗口中元素的索引，隊(duì)列左邊界記錄當(dāng)前滑動(dòng)窗口中最大元素的索引

• 當(dāng)隊(duì)列非空，左邊界出界時(shí)(滑動(dòng)窗口向右移導(dǎo)致的)，更新左邊界
• 當(dāng)隊(duì)列非空，將隊(duì)列中索引對應(yīng)的元素值比 num 小的移除，更新隊(duì)列
• 當(dāng)索引 i 大于 k-1，更新輸出結(jié)果

class Solution: 
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: 
        if not  nums: return [] 
        window ,res = [],[] 
        for i,x in enumerate(nums): 
            # 如果存在窗口 而且窗口的第一個(gè)數(shù) 不在這個(gè)范圍，就出去 
            if i >= k and window[0] <= i-k: 
                window.pop(0) 
            # 每次進(jìn)入窗口的和最后一個(gè)比較，如果大了，最后一個(gè)直接刪除 
            while window and nums[window[-1]] <= x: 
                window.pop() 
            # 無論是不是刪除最后一個(gè)，都要加入x到窗口中 
            window.append(i) 
            # 如果出了窗口，就把窗口的頭加入到res中 
            if i >= k-1: 
                res.append(nums[window[0]]) 
        return res 

LeetCode 第 3 題 無重復(fù)字符的最長子串

給定一個(gè)字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度。

# 示例 1: 
# 輸入: "abcabcbb" 
# 輸出: 3 
#解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。 
# 示例 2: 
# 輸入: "bbbbb" 
#輸出: 1 
#解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1。 
# 示例 3 
# 輸入: "pwwkew" 
#輸出: 3 
#解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "wke"，所以其長度為 3。 
#請注意，你的答案必須是 子串 的長度，"pwke" 是一個(gè)子序列，不是子串。 

下面我們看看，“滑動(dòng)窗口”如何進(jìn)行字符串處理。結(jié)合題目中的例子“abcabcbb”這個(gè)字符串，我們來看看如何找它的無重復(fù)最長子串。

首先，我們定義窗口的兩端：begin和end，分別表示要找的子串的開頭和結(jié)尾。

開始的時(shí)候，begin和end都指向0的位置即‘a’，然后end不斷后移(窗口變寬)，當(dāng)遇到第二個(gè)‘a’時(shí)(遇見重復(fù)字符)就得到一個(gè)子串，其長度就是end和begin位置的差。

如何判斷是否遇到了重復(fù)字符‘a’呢?需要一個(gè)字典作為輔助數(shù)據(jù)結(jié)構(gòu)，把end從頭開始遇到的每個(gè)字符及其索引位置都放到字典里面，end每次移動(dòng)到新字符就查一下字典即可

class Solution: 
    def lengthOfLongestSubstring(self, s: str) -> int: 
        # 定義兩個(gè)變量res和start,res用于存儲(chǔ)最長子字符串的長度，start存儲(chǔ)無重復(fù)子串左邊的起始位置。 
        ''' 
        然后創(chuàng)建一個(gè)哈希表，遍歷整個(gè)字符串，如果字符串沒有在哈希表中出現(xiàn)，說明沒有遇到過該字符，則此時(shí)計(jì)算最長無重復(fù)子串，當(dāng)哈希表中的值小于left，說明left位置更新了，需要重新計(jì)算最長無重復(fù)子串。每次在哈希表中將當(dāng)前字符串對應(yīng)的賦值加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 

人生最重要的不是所站的位置，而是內(nèi)心所朝的方向。只要我在每篇博文中寫得自己體會(huì)，修煉身心;在每天的不斷重復(fù)學(xué)習(xí)中，耐住寂寞，練就真功，不畏艱難，奮勇前行，不忘初心，砥礪前行，人生定會(huì)有所收獲，不留遺憾 (作者：Runsen )

本文已收錄 GitHub  https://github.com/MaoliRUNsen/runsenlearnpy100