---
title: "239. Sliding Window Maximum"
url: "https://laigary.com/interview/coding/239-sliding-window-maximum"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2024-03-09"
tags: ["Sliding Window"]
---

# 239. Sliding Window Maximum

[239\. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/)

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

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

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

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

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

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

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

做法如下：

選用的資料結構是 queue

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

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

這個時候 queue 的意義為：

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

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

```python
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
```