LeetCode 239 Sliding Window Maximum - Example and Complexity Analysis

Trace nums = [1, 3, -1, -3, 5] with k = 3.

Deque stores indices. Initialize empty.

i = 0: Add 0. Deque: [0]. Window incomplete.

i = 1: nums[1] = 3 > nums[0] = 1. Pop 0. Add 1. Deque: [1]. Window incomplete.

i = 2: nums[2] = -1 < nums[1] = 3. Add 2. Deque: [1, 2]. Window [1, 3, -1]. Max = nums[1] = 3. Output: [3].

i = 3: nums[3] = -3 < nums[2] = -1. Add 3. Deque: [1, 2, 3]. Front index 1 is outside window (window is indices 1-3). Pop front. Deque: [2, 3]. No wait, index 1 is within [1, 2, 3]. Max = nums[2] = -1? Actually max is 3 at index 1. Let me recheck...

Actually window indices are [1, 2, 3] for the second output. Index 1 is valid. Max = nums[1] = 3. Output: [3, 3].

Each element enters and exits deque once. $O(n)$ time. Deque holds at most $k$ indices. $O(k)$ space.