This Java program uses a deque to solve the problem of finding the maximum in each sliding window of size k within a given array. The deque stores indices of the array elements and helps maintain the maximum values in each window.

Program Explanation

The program structure includes the following components:

• Main Class and Method: Execution starts in the main method where we define the array and window size.
• Sliding Window Maximum Function: This function handles the logic for finding the maximums using a deque.
• Deque Usage: The deque stores indices of the array elements, not the elements themselves. This allows us to efficiently manage and compare only relevant elements of the window.

Java Code

import java.util.Deque;
import java.util.LinkedList;

public class SlidingWindowMaximum {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = maxSlidingWindow(nums, k);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }

    public static 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];
        int ri = 0;
        // Store indices
        Deque<Integer> q = new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {
            // Remove numbers out of range k
            while (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            // Remove smaller numbers in k range as they are useless
            while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
                q.pollLast();
            }
            // q contains index... result contains content
            q.offer(i);
            if (i >= k - 1) {
                result[ri++] = nums[q.peek()];
            }
        }
        return result;
    }
}

How the Program Works

The maxSlidingWindow function performs several critical tasks:

1. It initializes a deque that will store the indices of the array elements.
2. For each element in the array, it removes indices that are out of the current window and removes elements from the deque that are less than the current element since they cannot be part of the maximum.
3. It then adds the current element’s index to the deque and if the window is at least size k, it adds the maximum for that window to the result array.

Explanation

• Deque Operations: The deque is used to store indices to efficiently get the maximum element in the current window. We only keep indices of elements that could potentially be the maximum in the current or future windows. Elements are added to the rear of the deque, and we remove elements from the front if they are outside the current window’s range.
• Time Complexity: The complexity of this approach is O(n) because each element is added and removed from the deque exactly once.
• Space Complexity: The space complexity is O(k) due to storing up to k elements in the deque.

Conclusion

This implementation is efficient, with a time complexity of O(n), where n is the number of elements in the array. This approach ensures that each element is processed a minimal number of times.