239. Sliding Window Maximum

Problem Description

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return an array of the maximum element in each sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7     3
 1 [3  -1  -3] 5  3  6  7     3
 1  3 [-1  -3  5] 3  6  7     5
 1  3  -1 [-3  5  3] 6  7     5
 1  3  -1  -3 [5  3  6] 7     6
 1  3  -1  -3  5 [3  6  7]    7

Example 2:

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

Constraints:

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 1 <= k <= nums.length

Python Solution

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # Use deque to store indices of potential maximum values
        deque = collections.deque()
        result = []
        
        for i in range(len(nums)):
            # Remove indices that are out of the current window
            while deque and deque[0] < i - k + 1:
                deque.popleft()
                
            # Remove indices whose values are less than the current value
            while deque and nums[deque[-1]] < nums[i]:
                deque.pop()
                
            # Add current index
            deque.append(i)
            
            # Add maximum of current window to result
            if i >= k - 1:
                result.append(nums[deque[0]])
                
        return result

Java Solution

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // Use deque to store indices of potential maximum values
        Deque deque = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];
        int j = 0;
        
        for (int i = 0; i < nums.length; i++) {
            // Remove indices that are out of the current window
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            
            // Remove indices whose values are less than the current value
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            // Add current index
            deque.offerLast(i);
            
            // Add maximum of current window to result
            if (i >= k - 1) {
                result[j++] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

C++ Solution

class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        // Use deque to store indices of potential maximum values
        deque deque;
        vector result;
        
        for (int i = 0; i < nums.size(); i++) {
            // Remove indices that are out of the current window
            while (!deque.empty() && deque.front() < i - k + 1) {
                deque.pop_front();
            }
            
            // Remove indices whose values are less than the current value
            while (!deque.empty() && nums[deque.back()] < nums[i]) {
                deque.pop_back();
            }
            
            // Add current index
            deque.push_back(i);
            
            // Add maximum of current window to result
            if (i >= k - 1) {
                result.push_back(nums[deque.front()]);
            }
        }
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    // Use array as deque to store indices of potential maximum values
    const deque = [];
    const result = [];
    
    for (let i = 0; i < nums.length; i++) {
        // Remove indices that are out of the current window
        while (deque.length && deque[0] < i - k + 1) {
            deque.shift();
        }
        
        // Remove indices whose values are less than the current value
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }
        
        // Add current index
        deque.push(i);
        
        // Add maximum of current window to result
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }
    
    return result;
};

C# Solution

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        // Use LinkedList as deque to store indices of potential maximum values
        LinkedList deque = new LinkedList();
        int[] result = new int[nums.Length - k + 1];
        int j = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            // Remove indices that are out of the current window
            while (deque.Count > 0 && deque.First.Value < i - k + 1) {
                deque.RemoveFirst();
            }
            
            // Remove indices whose values are less than the current value
            while (deque.Count > 0 && nums[deque.Last.Value] < nums[i]) {
                deque.RemoveLast();
            }
            
            // Add current index
            deque.AddLast(i);
            
            // Add maximum of current window to result
            if (i >= k - 1) {
                result[j++] = nums[deque.First.Value];
            }
        }
        
        return result;
    }
}