Monotonic Queue

Concept

A Monotonic Queue is a specialized Deque (Double-Ended Queue) where the elements inside are always sorted (either increasing or decreasing).

To maintain this property while iterating through an array, we perform clean-up operations on both ends:

1. The Back (The “Useless” Check): Before adding a new element X, we remove all elements at the back that are “worse” than X (e.g., smaller than X if we want the Max). Why? Because X is newer and better; the old small ones will never be the maximum again.
2. The Front (The “Expired” Check): We remove the element at the front if it has fallen out of the current sliding window range.

Problem: Sliding Window Maximum

Given an array nums and a window size k, find the maximum value in the window at each step.

• Naive Approach: Calculate max() for every window. Time: $O(N\cdot K)$. Too slow.
• Monotonic Queue Approach: Time: $O(N)$.

Input: [1, 3, -1, -3, 5], k=3

Index i	Value	Deque (Indices)	Logic	Result
0	1	[0]	Push 0.	-
1	3	[1]	1 < 3, so Pop 0. Push 1.	-
2	-1	[1, 2]	-1 < 3, keep 1. Push 2.	Max: 3
3	-3	[1, 2, 3]	-3 < -1, keep 2. Push 3. Front (1) is valid (1+3 != 3).	Max: 3
4	5	[4]	5 is huge. Pop 3, 2, 1. Push 4.	Max: 5

---

Implementation

from collections import deque
 
 
def max_sliding_window(nums: list[int], k: int) -> list[int]:
    q = deque()  # Stores INDICES
    result = []
 
    for i, n in enumerate(nums):
        # 1. Pop smaller elements from back (Maintain Decreasing Order)
        while q and nums[q[-1]] < n:
            q.pop()
 
        q.append(i)
 
        # 2. Pop expired elements from front
        # Logic: If front index + k == current index, it's too old.
        # Example: k=3. At i=3, index 0 expires (0+3==3).
        if q[0] + k == i:
            q.popleft()
 
        # 3. Add to result if window is full size
        if i >= k - 1:
            result.append(nums[q[0]])
 
    return result

use std::collections::VecDeque;
 
pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let mut queue: VecDeque<usize> = VecDeque::new();
    let mut result: Vec<i32> = Vec::new();
    let k_usize = k as usize; // Cast once for optimization
 
    for (i, &n) in nums.iter().enumerate() {
        // 1. Maintain Monotonic Decreasing (Pop Back)
        while !queue.is_empty() && nums[*queue.back().unwrap()] < n {
            queue.pop_back();
        }
 
        queue.push_back(i);
 
        // 2. Remove Expired (Pop Front)
        // Check: If the oldest index + k matches current i, it's out.
        if *queue.front().unwrap() + k_usize == i {
            queue.pop_front();
        }
 
        // 3. Record Result
        if i >= k_usize - 1 {
            result.push(nums[*queue.front().unwrap()]);
        }
    }
    result
}

When to use this pattern?

You should trigger the Monotonic Queue pattern when you see these requirements:

1. “Sliding Window” + “Extremes”: You need the Minimum or Maximum of a subarray of fixed size k moving across the data.
2. “Shortest Subarray with Sum >= K”: (LeetCode 862). This is a harder variation that requires a Monotonic Queue to optimize the start pointer of the window.
3. “Optimization with Constraints”: E.g., “Find the max score you can get by jumping at most k steps.” (DP + Monotonic Queue).

Key Difference from Monotonic Stack:

• Stack: Used for “First element larger/smaller than me” (Boundaries).
• Queue: Used for “Best element within a range/window”.