Sliding Window Maximum

239.Sliding Window Maximum

Array

Sliding Window

Monotonic Queue

Problem Statement:

Given an array nums and a sliding window of size k moving from the left of the array to the right, return an array containing the maximum element in each window.

Example:

Input:

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

→

Output:

[3,3,5,5,6,7]

Java Solution:

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0) return new int[]{};
    
    LinkedList<Integer> q = new LinkedList<>();  // Monotonic queue
    int[] res = new int[nums.length - k + 1];
    
    for (int i = 0; i < nums.length; i++) {
        // Remove indices outside current window
        while (!q.isEmpty() && q.peekFirst() == i - k) 
            q.poll();
        
        // Maintain decreasing monotonic queue
        while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) 
            q.removeLast();
        
        // Add current index
        q.offer(i);
        
        // Store maximum for current window
        if (i + 1 >= k) 
            res[i - k + 1] = nums[q.peekFirst()];
    }
    
    return res; 
}

Python Solution:

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    if not nums: return []
    
    deque = collections.deque()  # Store indices
    result = []
    
    for i in range(len(nums)):
        # Remove indices outside window
        while deque and deque[0] == i - k:
            deque.popleft()
            
        # Maintain decreasing monotonic queue
        while deque and nums[deque[-1]] < nums[i]:
            deque.pop()
            
        deque.append(i)
        
        # Add maximum of current window
        if i >= k - 1:
            result.append(nums[deque[0]])
            
    return result

C++ Solution:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> result;
        
        for(int i = 0; i < nums.size(); i++) {
            // Remove indices outside window
            while(!dq.empty() && dq.front() == i - k)
                dq.pop_front();
                
            // Maintain decreasing monotonic queue
            while(!dq.empty() && nums[dq.back()] < nums[i])
                dq.pop_back();
                
            dq.push_back(i);
            
            if(i >= k - 1)
                result.push_back(nums[dq.front()]);
        }
        
        return result;
    }
};

Explanation:

Uses a monotonic queue (deque) to maintain a decreasing sequence of potential maximum values. The front of the queue always contains the index of the current window's maximum value. We remove elements from the back that are smaller than the current element (as they can never be the maximum) and remove elements from the front that are outside the current window.

Complexity:

Time: O(n) | Space: O(k)