合縱連橫: 從滿足特定條件的區間 理解 滑動窗口 背後的本質

Bao Menglong on Unsplash

這篇文章，會帶著大家複習以前學過的滑動窗口(Sliding window)框架，

並且滿足特定區間的概念與應用為核心，

貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。

滑動窗口(Sliding window)框架示意圖

滑動窗口(Sliding window)的框架

left = 0

# 右端點持續往右滑動，掃描每個元素​
for right, value in enumerate( array ):
	
		更新窗口資訊​
	
		while 為了滿足特定條件，窗口需要收縮時:
			收縮窗口
			更新窗口資訊
			left += 1
		
		現在滿足條件了，可以更新答案​
	
return 最終答案​
		​	​

用途:

找出滿足條件的最小區間長度。

找出滿足條件的最大區間長度。

找出滿足條件的區間總數目。

接下來，我們會用這個上面這種框架，貫穿一些同類型，有關聯的題目

(請讀者、或觀眾留意上面的這種 前綴和 框架，之後的解說會反覆出現)

Longest Substring Without Repeating Characters
字元不重複的最大區間長度

這題的特定條件是什麼? 要求字元不重複！

那關鍵資訊在哪裡呢?

其實就是每個字元的最後一次出現位置。

當我們往右掃描字元的時候，如果發現某個字元的最後一次出現位置落在窗口內時，

代表已經重複，必須收縮左窗口，直到沒有重複為止。

使用滑動窗口，配合字典來記錄每個字元的最後一次出現位置。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        last_seen = defaultdict(lambda: -1)
        left, window_size = 0, 0

        for right, char in enumerate(s):
							
							# 發現有重複字元，收縮左窗口​
            while last_seen[char] >= left:
                left += 1

            window_size = max( window_size, right-left+1)
            last_seen[ char ] = right

        return window_size 

還有一個最佳化的小技巧，當我們發現，收縮是有規律的時候，
可以一步到位，直接收縮到最接近的合法位置。

這一題是要求字元不重複，所以最接近的合法位址，就是重複字元出現位置的右手邊。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        last_seen = defaultdict(lambda: -1)
        left, window_size = 0, 0

        for right, char in enumerate(s):
							
							# 最接近的合法位址，就是重複字元出現位置的右手邊。​
            if last_seen[char]>= left:
                left = last_seen[char] + 1

            window_size = max( window_size, right-left+1)
            last_seen[ char ] = right

        return window_size 

Length of Longest Subarray With at Most K Frequency
區間內的字元最多出現k次的最大區間長度

這題的特定條件是什麼? 要求每個字元出現次數最多k次！

那關鍵資訊在哪裡呢?

其實就是每個字元窗口內的出現次數。

當我們往右掃描字元的時候，如果發現某個字元的出現次數>k時，

代表已經不滿足條件，必須收縮左窗口，直到窗口內的字元出現次數都<=k為止。

使用滑動窗口，配合字典來記錄每個字元窗口內的出現次數。

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        
        ## Dictionary
        # key: character
        # value: occurrence
        occurrence = defaultdict(int)

        left, window_length = 0, 0
        
        # Scan each character from left to right
        for right, char in enumerate(nums):

            occurrence[char] += 1
							
							# 當現在這個字元出現次數>k時，收縮窗口
            # Shirnk sliding window if occurrence is larger than k
            while occurrence[char] > k:
                occurrence[ nums[left] ] -= 1
                left += 1
            
            # Update length of sliding window
            window_length = max(window_length, right - left + 1) 
        
        return window_length

Fruit Into Baskets 最多只能摘兩種水果的情況下，可以摘多少水果?

這題的特定條件是什麼? 要求最多只能摘兩種水果！

那關鍵資訊在哪裡呢?

其實就是目前摘了幾種水果。

當我們往右掃描摘水果的時候，如果發現已經摘了三種水果，

代表已經不滿足條件，必須收縮左窗口，直到回到最多只摘兩種水果為止。

使用滑動窗口，配合字典來記錄每種水果在窗口內的出現次數。

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        
        left, collect = 0, 0

        occurrence = defaultdict(int)

        for right, fruit_type in enumerate(fruits):

            occurrence[ fruit_type ] += 1
            
            # 已經摘了三種水果，必須收縮窗口
            while len(occurrence) > 2:
                occurrence[ fruits[left] ] -= 1
                
                if occurrence[ fruits[left] ] == 0:
                    del occurrence[ fruits[left] ]

                left += 1

            collect = max(collect, right - left + 1)
        
        return collect

結語

好，今天一口氣介紹了最精華的部分，

通用的滑動窗口框架，還有相關的滿足特定區間應用題與演算法建造，

希望能幫助讀者、觀眾徹底理解它的原理，

並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！

感謝收看囉! 我們下篇文章再見~