Monotonic Queue (Deque) Pattern in Java — A Detailed Guide

Monotonic deque extends monotonic-stack thinking to moving windows. It gives fast max/min queries while the window slides.

---

Core Idea

Maintain deque of indices with monotonic values.

For window maximum:

• front always stores index of maximum
• pop front if out of window
• pop back while incoming value is larger

---

Template: Sliding Window Maximum

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k <= 0) return new int[0];
    if (k == 1) return Arrays.copyOf(nums, nums.length);
    int n = nums.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();
    int idx = 0;

    for (int r = 0; r < n; r++) {
        while (!dq.isEmpty() && dq.peekFirst() <= r - k) dq.pollFirst();
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[r]) dq.pollLast();
        dq.offerLast(r);
        if (r >= k - 1) ans[idx++] = nums[dq.peekFirst()];
    }
    return ans;
}

---

Problem 1: Sliding Window Maximum

Same as template above. Time O(n).

---

Problem 2: Sliding Window Minimum

public int[] minSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] ans = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();
    int idx = 0;

    for (int r = 0; r < n; r++) {
        while (!dq.isEmpty() && dq.peekFirst() <= r - k) dq.pollFirst();
        while (!dq.isEmpty() && nums[dq.peekLast()] >= nums[r]) dq.pollLast();
        dq.offerLast(r);
        if (r >= k - 1) ans[idx++] = nums[dq.peekFirst()];
    }
    return ans;
}

---

Problem 3: Shortest Subarray With Sum At Least K

This combines prefix sums + increasing deque.

public int shortestSubarray(int[] nums, int k) {
    int n = nums.length;
    long[] pre = new long[n + 1];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];

    int best = n + 1;
    Deque<Integer> dq = new ArrayDeque<>();

    for (int i = 0; i <= n; i++) {
        while (!dq.isEmpty() && pre[i] - pre[dq.peekFirst()] >= k) {
            best = Math.min(best, i - dq.pollFirst());
        }
        while (!dq.isEmpty() && pre[i] <= pre[dq.peekLast()]) {
            dq.pollLast();
        }
        dq.offerLast(i);
    }

    return best == n + 1 ? -1 : best;
}

---

Common Mistakes

1. Storing values instead of indices
2. Not removing out-of-window indices first
3. Wrong inequality direction when maintaining monotonicity
4. Treating deque operations as arbitrary instead of invariant-driven

---

Debugging Deque State

When output is wrong, print deque as (index:value) at each step:

r=5 in=9 dq=[3:7,4:8] -> popBack 4, popBack 3, push 5

Verify three operations happen in order:

1. remove expired front indices
2. enforce monotonicity at back
3. append current index

This order is crucial for correctness.

---

Practice Set (Recommended Order)

1. Sliding Window Maximum (LC 239)
   LeetCode
2. Shortest Subarray with Sum at Least K (LC 862)
   LeetCode
3. Constrained Subsequence Sum (LC 1425)
   LeetCode
4. Jump Game VI (LC 1696)
   LeetCode
5. Longest Continuous Subarray with Absolute Diff <= Limit (LC 1438)
   LeetCode

---

Key Takeaways

• Monotonic deque is the standard for window extrema in linear time.
• The deque invariant guarantees correctness and amortized O(1) updates.
• It is a critical pattern for advanced sliding-window and DP problems.