Efficient Interval Extremum Maintenance: Core Principles and Implementation Guide of Monotonic Queue

Core Logic and Mathematical Principles

A Monotonic Queue is essentially a data structure that maintains the extremum of an interval. The core idea is: If, in the current window, an old element's lifespan is shorter than that of a new element and its value is not superior to the new element, then the old element will never be the extremum of the interval.

For the problem of finding the maximum value in an interval, let the right endpoint of the current window be $i$, and the left endpoint be $ ext{max}(1, i-k+1)$. The queue stores the indices of the array. For any two adjacent element indices $x$ and $y$ in the queue (where $x$ was enqueued before $y$, i.e., $x < y$), it must hold that:

$$A[x] ext{ ≥ } A[y]$$

When a new element $A[i]$ attempts to enter the queue, it is necessary to pop all elements from the tail that satisfy $A[ ext{tail}] < A[i]$ to maintain the monotonicity of the queue.

In terms of time complexity, each element can be enqueued at most once and dequeued at most once. Therefore, even with an internal while loop, its amortized time complexity is strictly:

$$O(N)$$

The space complexity is:

$$O(N)$$

State Design and Pitfalls of std::deque

1. State Design and Operations of the Deque

The queue does not store the values of the array directly, but rather stores the indices of the array. This is because indices can provide both value information (via $A[ ext{index}]$ indexing) and lifespan information (by checking $i - ext{index} ext{ ≥ } k$ to determine if it has expired).

• Head Check: If $ ext{head extunderscore index} ext{ ≤ } i - k$, it indicates that the element has slid out of the window, and we perform a head dequeue.
• Tail Purging: If the current element $A[i]$ is superior to the tail element, we keep popping from the tail until we satisfy monotonicity or the queue is empty.
• New Enqueue: Push the current index $i$ to the tail.
• Get Extremum: The element corresponding to the head is the current window's extremum.

2. Pitfalls of std::deque

In competitions like NOIP with strict time limits, it is strictly prohibited to use std::deque from the standard template library directly.

• Memory Fragmentation and Huge Constants: std::deque does not store memory contiguously but uses a segmented structure. Its internal pointer overloading and frequent dynamic memory allocations lead to significant constant overhead. With data sizes of $10^6$, the time taken by std::deque is typically $3$ to $5$ times that of a manually implemented array-based queue, making it prone to TLE due to lag.
• Alternative Solution: You must use a native array to simulate the deque. Use two pointers head and tail to point to the head and tail, respectively, with operations being $O(1)$ pointer movements, which are very CPU cache-friendly.

C++ Standard Source Code (NOIP Style)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 1000005;
int a[MAXN];
int q[MAXN]; // Manual array simulating the deque, storing indices

int main() {
    // Optimize standard input/output stream for faster I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // First pass: find the minimum value in the interval
    int head = 1, tail = 0; // Initialize as an empty queue
    for (int i = 1; i <= n; ++i) {
        // 1. Check head validity: remove elements that have slid out of the window
        if (head <= tail && q[head] <= i - k) {
            head++; 
        }
        // 2. Maintain tail monotonicity: if the new element is smaller, the old element has no chance
        while (head <= tail && a[q[tail]] >= a[i]) {
            tail--; // Critical point: must be >= instead of >, equal elements retain the latter's lifespan longer
        }
        // 3. Enqueue the current element index
        q[++tail] = i;
        // 4. Output the answer when the window is complete
        if (i >= k) {
            cout << a[q[head]] << (i == n ? "" : " ");
        }
    }
    cout << "\n";

    // Second pass: find the maximum value in the interval
    head = 1, tail = 0; 
    for (int i = 1; i <= n; ++i) {
        if (head <= tail && q[head] <= i - k) {
            head++;
        }
        while (head <= tail && a[q[tail]] <= a[i]) {
            tail--; // Maintain monotonicity, new element larger, remove from tail
        }
        q[++tail] = i;
        if (i >= k) {
            cout << a[q[head]] << (i == n ? "" : " ");
        }
    }
    cout << "\n";

    return 0;
}

NOIP Practical Pitfall Guide

1. Queue Boundary Overflow and Infinite Loops

When simulating a queue with an array, the while loop condition must first check if the queue is empty, i.e., head <= tail.

// Incorrect Example
while (a[q[tail]] >= a[i]) tail--; 

If the head <= tail restriction is not added, when the input sequence is monotonically decreasing (when finding the minimum) or monotonically increasing, tail will continuously decrement to become negative, leading to array out-of-bounds access (RE) or falling into an infinite loop due to abnormal memory data.

2. Extreme Boundary Cases of Window Size $k > n$

In some variant problems, the window size $k$ may change dynamically, or initially $k > n$. If you directly execute if (i >= k) for output without control, it will result in no output at all, leading to a direct zero score in evaluations. The code must include boundary checks between $k$ and $n$, or adaptively adjust the effective window boundaries according to problem requirements.

Classic NOIP/Luogu Problems

1. Luogu P1886 Sliding Window / [Template] Monotonic Queue

• Problem Description: Given an array of length $n$ and a window of size $k$. The window slides from the leftmost side to the rightmost side, moving one position to the right each time. Find the maximum and minimum values in the window after each move.
• Core Essence: Pure static interval extremum maintenance.
• Core Solving Idea: Standard monotonic queue template. Two passes, the first maintaining a monotonic increasing queue to find the minimum, and the second maintaining a monotonic decreasing queue to find the maximum. Strictly utilize array simulation to ensure $O(n)$ complexity fills the time limit.

2. Luogu P2216 [HAOI2007] Ideal Square

• Problem Description: Given an integer matrix of size $a imes b$, find a $n imes n$ square region within it such that the difference between the maximum and minimum values in that region is minimized.
• Core Essence: Two-dimensional sliding window extremum problem.
• Core Solving Idea: Two-dimensional monotonic queue. First, perform a one-dimensional sliding window (length $n$) on each row of the matrix, using the monotonic queue to find the maximum and minimum values in each row's intervals, storing the results in an auxiliary matrix $B$. Then, perform a one-dimensional sliding window (length $n$) on each column of the auxiliary matrix $B$. By combining two one-dimensional monotonic queues, the two-dimensional extremum problem can be resolved in $O(a imes b)$ time complexity.