題目出處

難度

hard

個人範例程式碼

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) < k:
            return []

        queue_idx = []
        ans = []

        # 1. if i-k == queue_idx[0] (3-3 = 0) oversize, pop oldest (0)
        # 2. if +1 nums[queue_idx[-1]] < num, remove smaller
        # 3. append new element
        # 4. nums[queue_idx[0]] will be max

        for i, num in enumerate(nums):
            # 1. if i-k == queue_idx[0] (3-3 = 0) oversize, pop oldest (0)
            if queue_idx and i - k == queue_idx[0]:
                queue_idx.pop(0)

            # 2. if +1 nums[queue_idx[-1]] < num, remove smaller
            while queue_idx and nums[queue_idx[-1]] < num:
                queue_idx.pop(-1)

            # 3. append new element
            queue_idx.append(i)

            # 4. nums[queue_idx[0]] will be max
            if i+1 >= k: # 2+1 >= 3
                ans.append(nums[queue_idx[0]])    

        return ans

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

暴力解的版本，會在每次的 find max 花太多時間，
而我們會發現，sliding window 的特性，我們應該可以達成最小化的重複性更改。

基本上我們可以拆成四大步驟：

queue_idx[0] (3-3 = 0) oversize, pop oldest (0)

input handling

如果 len(nums) < k，則不可能組出 window。

Boundary conditions

用 for 控制範圍

個人範例程式碼 - 暴力解，會 TLE

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) < k:
            return []

        ans = []
        slow, fast = 0, k    
        counter = defaultdict(int)
        # init counter
        for i in range(k):
            counter[nums[i]] += 1
        ans.append(self.get_counter_max(counter))

        # sliding window
        while fast < len(nums):
            counter[nums[slow]] -= 1 
            counter[nums[fast]] += 1
            ans.append(self.get_counter_max(counter))
            slow += 1 
            fast += 1

        return ans

    # O(n), if sorting O(nlogn)        
    def get_counter_max(self, counter):
        get_max = float("-inf")
        for key in counter.keys():
            if counter[key] > 0:
                get_max = max(get_max, key)

        return get_max