239. Sliding Window Maximum

Last updated on Mar 9, 2024

這個題目是滑動窗口的問題，最糟糕的方式是透過兩個迴圈去分別找出最大值，我覺得面試時是合理可以去先用窮舉的方式先寫出最基本的答案的，這題存在著進階的解法，但是要想到解法滿困難的，而且實作上也有一定的困難度。

這一題的困難點是，當窗口滑動後，不在這個窗口內的值，就不需要去考量是否是該窗口的最大值了，如果有一個窗口不斷的紀錄目前該窗口有哪些值，要去移除不在窗口的值其實並不困難，但是這一題造成複雜的是在窗口移動的過程中：

最大值可能沒有改變
又或是被移出窗口的值剛好是最大值，需要重新看該窗口的最大值是什麼

所以這個題目不能只是單純的只有紀錄最大值，因為如果只有紀錄最大值，就會造成第二點的情況，所以需要設計的是如何同時得知最大值的同時，又知道該值是在該窗口內。

所以在這裡可以考量的策略，其實可能不是去紀錄值，因為知道最大值，值沒有辦法重新找回 index ，所以就很難確認區間，但是如果我們能夠紀錄 index ，很好找到該 index 對應的值，接著只要再去想怎麼有效率的紀錄 index 就好。

接下來的步驟其實並不容易去想，我只能用猜的去看看面試時會不會有辦法想到

這個資料結構「應該」會和滑動窗口的概念很類似，會是一個 FIFO 的資料結構。
要想到如何及時更新這個資料結構的狀態。

做法如下：

選用的資料結構是 queue

每次移動一個窗口的時候，檢查 queue 的第一個元素是否還在窗口內？因為先進先出的概念，在滑動窗口時 queue 最前面的元素都會是更早的窗口的元素。
1. 這時候我們會知道如果queue內就是還是屬於這個窗口的「最大值」的元素
接著是更新的策略
1. 如果要放進去的值比該窗口所有的數值都大的時候，我們應該要把之前紀錄的所有的值都放棄。
2. 如果要放進去的值雖然沒有所有的數值都大，但是比之前紀錄到的某些數字還來得大的時候，那些數字都應該要放棄，直到遇到比我大的數字為止。
3. 並且應該也要紀錄起來現在這個值，為什麼要紀錄起來呢？因為一些更大的數字，可能在移動窗口的過程中，會被刪除，此時這個數字可以會是之後的最大值的候選人。

其實如果能想到上述第二大項的整體邏輯後，這個題目就可以寫出來了。

這個時候 queue 的意義為：

第一項為當前窗口最大值的 index ，當前的窗口中絕對不會有更大的是因為 2b
第一項之後只是為候選人，也有可能再下次的更新時，全部都被刪掉。

題目的最後是，為什麼下面的寫法還有一個 i >= k - 1 的檢查？因為我們在檢查到第 k 個元素後，才會放入第一個最大值到答案中，而 k - 1 是該數字的位置。

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

        queue = deque()
        ans = []
        for i in range(n):
            while queue and queue[0] == i - k:
                queue.popleft()
            while queue and nums[i] > nums[queue[-1]]:
                queue.pop()
            queue.append(i)
            if i >= k - 1:
                ans.append(nums[queue[0]])
        return ans