Sliding Window Maximum

LeetCode 239 · View on LeetCode

Use a deque (monotonic decreasing) to track the index of the current maximum. Remove elements outside the window from the front and smaller elements from the back.

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq = deque()  # indices, front is always the max
    result = []
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] <= num:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

if __name__ == '__main__':
    print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))  # [3,3,5,5,6,7]
    print(max_sliding_window([1], 1))                            # [1]
    print(max_sliding_window([9, 11], 2))                        # [11]