LeetCode 239: Sliding Window Maximum

Explanation:

To solve this problem, we can use a deque (double-ended queue) to store the indices of the elements in the current window. We maintain the deque in such a way that the front of the deque always contains the index of the maximum element in the current window.

At each step, we do the following:

1. Remove indices from the front of the deque that are outside the current window.
2. Remove indices from the back of the deque that correspond to elements smaller than the current element.
3. Add the index of the current element to the back of the deque.

The front of the deque will always contain the index of the maximum element in the current window. We add this maximum element to the result whenever the window size reaches k.

Time Complexity:

The time complexity of this approach is O(n) where n is the number of elements in the input array.

Space Complexity:

The space complexity is O(n) as we are using a deque to store indices.

:

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) return new int[0];
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        
        int rIdx = 0;
        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offer(i);
            if (i >= k - 1) {
                result[rIdx++] = nums[deque.peek()];
            }
        }
        
        return result;
    }
}