Algorithm-Day11-Sliding-Window-Maximum-lc-239

🧩 Problem Description

You are given an array of integers nums, and there is a sliding window of size k that moves from the very left to the very right.

Return the maximum value in each window as it slides.

Example:

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

💡 Brute Force (Too Slow)

For each window, scan the k elements to find the max.

// O(n * k)
for (int i = 0; i <= nums.length - k; i++) {
    int max = Integer.MIN_VALUE;
    for (int j = i; j < i + k; j++) {
        max = Math.max(max, nums[j]);
    }
    result.add(max);
}

• ✅ Works
• ❌ Too slow when nums.length is large

---

💡 Optimal Approach: Monotonic Queue (Deque)

🧠 Key Idea

Use a deque (double-ended queue) to keep indices of elements in decreasing order:

• Front of deque always holds the index of the current maximum
• Before adding a new index, remove all indices whose values are less than the current number
• Remove indices that are out of the window

✅ Why a deque?

It helps us maintain a “candidate list” for the maximum of the current window — always in O(1) time per operation.

---

🔢 Java Code

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) return new int[0];

        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>(); // store indices

        for (int i = 0; i < nums.length; i++) {
            // Remove indices out of the current window
            if (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // Remove smaller elements (they’ll never be max)
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }

            deque.offerLast(i); // Add current index

            // Start recording results after first window is filled
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
  Each element is added and removed at most once from the deque
• Space Complexity: O(k)
  For the deque storing at most k elements

---

✍️ Summary

• The monotonic queue is a powerful technique for max/min in sliding windows
• Much more efficient than brute force (O(n) vs O(n × k))
• Common pattern in other problems like lc-862, lc-1438, and lc-1425

When dealing with “sliding window max/min”, always think of using a deque to maintain order.