Array - 239. Sliding Window Maximum

239. Sliding Window Maximum

Given an array 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 the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and 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

Note
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

Solution Approach：

1. Input Validation:

   • First, handle the edge cases by checking if the input array nums is null or if k is less or equal to 0. If so, return an empty array.

2. Initialization:

   • Initialize a result array res of size (len - k + 1) to store the maximum values of each window.
   • Initialize an index variable index to 0, which will be used to populate the result array.
   • Initialize a deque deque to help in keeping track of the maximum element in the current window.

3. Iterate Through the Array:

   • Iterate through the input array nums using a loop variable i.
   • In each iteration, perform the following steps:
     • Clean Up Deque:
       • Remove the first element from the deque if it is outside the current window (i.e., its index is less than i - k + 1).
       • Remove the last element from the deque if it is less than the current element, to maintain the deque in a decreasing order.
     • Update Deque:
       • Add the current element’s index i to the deque.
     • Populate Result Array:
       • If i is greater or equal to k - 1, it means the deque has k elements. Therefore, add the maximum element of the current window (which is at the front of the deque) to the result array.

4. Return the Result:

   • After the loop, return the result array res which now contains the maximum values of all sliding windows of size k.

This algorithm efficiently keeps track of the maximum element in each window of size k as it slides through the input array, using a deque to ensure a time complexity of O(n).

Code：

java：

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0 ) return new int[]{};
        
        int len = nums.length;
        int[] res = new int[len - k + 1];
        int index = 0;
        
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 0; i < len; i++){
        
            // Pop the first index from the deque if the deque size exceeds k.
            while(!deque.isEmpty() && deque.peek() < i - k +1) deque.poll();
            
            // Pop the last index from the deque to maintain monotonic(decreasing order). 
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
            
            // Add current index to deque end
            deque.offer(i);
            
            // Since i starts from 0, we must wait until the queue size is k to start populating the result array.
            if (i >= k-1) {
                res[index++] = nums[deque.peek()];
            }                          
        }
        return res;
    }                                       
}