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. time. Deque holds at most indices. space.