A monotonic queue is a specialized data structure that maintains elements in either strictly increasing or decreasing order. Unlike standard queues, a monotonic queue allows operations at both the front and rear, functioning as a double-ended queue (deque) where elements are kept in sorted order.

The Core Principle

The fundamental insight behind monotonic queues is straightforward: elements that are older and inferior can never become the optimal choice.

Consider finding the minimum value in a sliding window moving from left to right. When a new element arr[j] enters the window, compare it with existing elements. If an earlier element arr[i] satisfies arr[i] >= arr[j], then arr[i] is doomed—it will exit the window before arr[j], and for the remainder of its lifetime in the window, arr[j] will always be smaller. Thus, arr[i] can be safely discarded.

This elimination process ensures that for any two elements at positions i < j, the queue maintains arr[i] < arr[j]—a strictly monotonic increasing sequence.

Classic Application: Sliding Window Maximum

Given an array and a fixed window size k, find the maximum value in each window position. This is the canonical monotonic queue problem.

The algorithm proceeds in two steps for each new element:

1. Remove elements from the back that are no longer competitive (smaller than or equal to the new element for a maximum queue)
2. Remove elements from the front that have exited the window bounds

Here is a clean implementation:

#include <cstdio>
#include <deque>
using namespace std;

const int MAXN = 1000005;
int arr[MAXN];
int maxResult[MAXN], minResult[MAXN];

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // Compute sliding window minimum
    deque<int> minDeque;
    for (int i = 0; i < n; i++) {
        // Remove elements outside window from front
        while (!minDeque.empty() && minDeque.front() <= i - k) {
            minDeque.pop_front();
        }
        // Remove larger elements from back (maintain increasing order)
        while (!minDeque.empty() && arr[minDeque.back()] >= arr[i]) {
            minDeque.pop_back();
        }
        minDeque.push_back(i);
        
        if (i >= k - 1) {
            minResult[i - k + 1] = arr[minDeque.front()];
        }
    }
    
    // Compute sliding window maximum using negation trick
    for (int i = 0; i < n; i++) {
        arr[i] = -arr[i];
    }
    
    deque<int> maxDeque;
    for (int i = 0; i < n; i++) {
        while (!maxDeque.empty() && maxDeque.front() <= i - k) {
            maxDeque.pop_front();
        }
        while (!maxDeque.empty() && arr[maxDeque.back()] >= arr[i]) {
            maxDeque.pop_back();
        }
        maxDeque.push_back(i);
        
        if (i >= k - 1) {
            maxResult[i - k + 1] = -arr[maxDeque.front()];
        }
    }
    
    // Output results
    for (int i = 0; i <= n - k; i++) {
        printf("%d ", minResult[i]);
    }
    printf("\n");
    for (int i = 0; i <= n - k; i++) {
        printf("%d ", maxResult[i]);
    }
    
    return 0;
}

Each element enters and exits the queue at most once, yielding O(n) linear time complexity.

Dynamic Programming Optimization

Monotonic queues frequently optimize dynamic programming transitions where we need to find extremal values over a range. Consider this DP recurrence:

dp[i] = arr[i] + max(dp[j]) for j in range [i-R, i-L]

Naively computing the maximum for each state costs O(n) per state, leading to O(n²) total. However, this is precisely a sliding window maximum problem—applying a monotonic queue reduces this to O(n).

Example: Cirno's Game (P1725)

Given an array of values and movement constraints [L, R], find the maximum score achievable when moving from posision 0 to beyond position n. The transition involves finding the maximum DP value within a fixed range, making monotonic queue optimization natural.

Example: Power Collection (P3800)

In a grid where you can move up or down by at most t columns when moving right, maximize collected power. The transition:

dp[i][j] = grid[i][j] + max(dp[i-1][p]) for p in [j-t, j+t]

The inner maximum query spans a fixed-width window, optimized by monotonic queues for O(nm) complexity.

2D Sliding Window

For finding maximum/minimum in an n×n square region, apply monotonic queues in two passes:

1. First, compute row-wise extrema: for each row, find the max/min in windows of width n
2. Then, on this intermediate result, compute column-wise extrema with windows of height n

This two-phase approach reduces an O(n²) per square computation to O(nm) overall.

Beyond Fixed-Length Windows

The critical observation is that monotonic queues work whenever both window endpoints move monotonically. The window length can vary—what matters is that left and pointers only advance.

Consider a problem where for each position r, you need min(sum[l-1]) for l-1 in range [r-t, r-s]. Eventhough this range has variable width, the endpoints advance monotonically with r, enabling monotonic queue optimization.

Implementation Template

deque<int> dq;  // stores indices
int left = 0;

for (int right = 0; right < n; right++) {
    // Update left bound of valid range
    while (left < right && !isValid(left, right)) {
        left++;
    }
    
    // Remove outdated elements from front
    while (!dq.empty() && dq.front() < left) {
        dq.pop_front();
    }
    
    // Maintain monotonicity from back
    while (!dq.empty() && isWorse(dq.back(), right)) {
        dq.pop_back();
    }
    
    dq.push_back(right);
    
    // Front always holds the optimal element
    if (canQuery(right)) {
        process(dq.front());
    }
}

Note the order of operations: remove outdated elements before maintaining monotonicity. In some problems, newly added elements might not satisfy the window bounds—if monotonicity is enforced first, invalid elements could remain in the queue.

When to Apply Monotonic Queues

Monotonic queue optimization applies when:

• You need to find min/max over a range [l, r]
• Both endpoints l and r move monotonically (never decrease)

The most common scenario—sliding window with fixed length—is simply a special case where the range width remains constant.