Given an integer array nums and an integer k, a sliding window of size k traverses the array from left to right. Only the k numbers within the window are visible at any step, and the window shifts right by one position after each move. The task is to return the maximum element inside the window for every valid posiiton.

Example 1

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7]

Example 2

Input: nums = [1], k = 1 Output: [1]

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

Algorithm

A brute-force strategy that recomputes the maximum for every window independently runs in O(n · k) time and will time out for large inputs. The optimal approach uses a deque to maintain a monotonically decreasing sequence of indices.

As we iterate over nums, the deque stores candidate indices such that their corresponding values appear in strictly decreasing order. For each new index pos:

1. Remove the front element if it has exited the window (index <= pos - k).
2. Remove elements from the back while their values are less than or equal to nums[pos], because the current element dominates them and will remain valid longer.
3. Append pos to the back.
4. Once the first complete window is formed (pos >= k - 1), the front of the deque always points to the current maximum, so we record nums[deque.front()].

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> candidates;
        
        for (int pos = 0; pos < static_cast<int>(nums.size()); ++pos) {
            // Discard indices that slid out of the window boundary
            if (!candidates.empty() && candidates.front() <= pos - k) {
                candidates.pop_front();
            }
            
            // Preserve monotonic decreasing order by popping smaller rear elements
            while (!candidates.empty() && nums[candidates.back()] <= nums[pos]) {
                candidates.pop_back();
            }
            
            candidates.push_back(pos);
            
            // Start emitting maxima once the window is fully formed
            if (pos >= k - 1) {
                result.push_back(nums[candidates.front()]);
            }
        }
        
        return result;
    }
};