239. Sliding Window Maximum

To turn the usual $O(nk)$ solution into an $O(n)$ solution, think of keeping a maximum deque. We want to pop from the start and add to the end, but also we want to keep calculating the max to $O(1)$, so calculating the maximum lets us do that.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = deque()   # stores indices, nums[q[0]] is max
        res = []
 
        for i, num in enumerate(nums):
            # 1. remove smaller values at the back
            while q and nums[q[-1]] < num:
                q.pop()
 
            # 2. add current index
            q.append(i)
 
            # 3. remove leftmost if it’s out of window
            if q[0] <= i - k:
                q.popleft()
 
            # 4. record max once first window is ready
            if i >= k - 1:
                res.append(nums[q[0]])
 
        return res