NeFut Logo NeFut
中 Admin Login

Efficient Principles and Applications of Monotonic Stack and Queue

Published at: 2026-05-27 09:17 Last updated: 2026-06-06 13:04
#algorithm #Data Structure #C++

Core Logic and Mathematical Principles

Monotonic stacks and queues are linear data structures that maintain the monotonicity of elements. Their core physical models are dynamic turning point elimination and lifespan elimination.

In a monotonic stack, the addition of a new element can disrupt the existing monotonicity. If we require the elements in the stack to be monotonically increasing, when a new element $x$ is less than the top element of the stack, the top element is completely obscured (or replaced) by $x$ in subsequent comparisons, losing its potential as an optimal solution, and must be popped immediately. Each element can be pushed and popped at most once, resulting in an amortized time complexity of $O(N)$.

In a monotonic queue, the concept of "lifespan" is introduced, which refers to the boundary constraints of the sliding window. The monotonic queue maintains a double-ended queue, and its core physical model is the dynamic evolution of range minimum queries (RMQ). For two elements $A[i]$ and $A[j]$, if $i < j$ and $A[i] ext{ ≤ } A[j]$, as the window slides to the right, $A[i]$ is dominated by $A[j]$ in both size and lifespan. Therefore, $A[i]$ becomes a useless redundancy and needs to be removed from the back of the queue. Meanwhile, if the front element of the queue exceeds the left boundary of the window $L = i - K + 1$, it must be popped from the front due to expiration.

State Design and Algorithm Derivation

1. Monotonic Stack: Next Greater Element

Given the input sequence $A$, the goal is to find the index $R[i]$ of the first element greater than $A[i]$ to the right of each position $i$.

$$R[ ext{stk.top()}] = i$$

Perform the pop operation $ ext{stk.pop()}$, and repeat this process until the stack is empty or $A[i] ext{ ≤ } A[ ext{stk.top()}]$. Finally, push $i$ onto the stack.

2. Monotonic Queue: Sliding Window Maximum

Assuming the window size is $K$, we need to find the maximum value within the window ending at each position $i$.

  1. Remove Expired from Front: Given the current index $i$, if $ ext{q.front()} < i - K + 1$, it indicates that the front minimum value has slid out of the window, and we perform q.pop_front().
  2. Remove Redundant from Back: When the queue is not empty and $A[i] ext{ ≥ } A[ ext{q.back()}]$, the back element is removed as it is smaller and has a shorter lifespan.
  3. Enqueue and Decision: Push $i$ to the back of the queue. When $i ext{ ≥ } K - 1$, the current window maximum is given by $A[ ext{q.front()}]$.

C++ Standard Source Code

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

// Simulating Luogu P5788 [Template] Monotonic Stack
void solveMonotoneStack() {
    int n;
    if (!(cin >> n)) return;

    vector<int> a(n + 1);
    vector<int> r(n + 1, 0);
    vector<int> stk; 
    stk.reserve(n + 1); // Preallocate memory to avoid constant overhead from vector dynamic expansion

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

    for (int i = 1; i <= n; ++i) {
        // Key point: Trigger pop on strict greater, storing indices in the stack rather than values
        while (!stk.empty() && a[i] > a[stk.back()]) {
            r[stk.back()] = i;
            stk.pop_back();
        }
        stk.push_back(i);
    }

    for (int i = 1; i <= n; ++i) {
        cout << r[i] << (i == n ? "" : " ");
    }
    cout << "\n";
}

// Simulating Luogu P1886 Sliding Window / [Template] Monotonic Queue
void solveMonotoneQueue() {
    int n, k;
    if (!(cin >> n >> k)) return;

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

    deque<int> q; // Store indices

    // 1. Find the minimum value in the range
    for (int i = 0; i < n; ++i) {
        // Check front: Remove expired indices exceeding the left boundary of the sliding window
        if (!q.empty() && q.front() < i - k + 1) {
            q.pop_front();
        }
        // Check back: New element is smaller, old elements are both larger and older, directly eliminate
        while (!q.empty() && a[i] <= a[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);

        if (i >= k - 1) {
            cout << a[q.front()] << (i == n - 1 ? "" : " ");
        }
    }
    cout << "\n";
}

int main() {
    // Optimize standard input/output performance, disable synchronization with stdio to avoid constant slowdown
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Switch calls based on evaluation targets, this is just for demonstration
    solveMonotoneStack();

    return 0;
}

NOIP Practical Pitfall Guide

  1. Monotonic Queue Front Out-of-Bounds and Infinite Loops When handling the movement of the sliding window, beginners often mistakenly write if (q.front() == i - k). This exact match can lead to missed judgments when dealing with dynamic interval movements that do not step by 1 or when there are non-standard data jumps mid-way, causing the queue to retain expired illegal indices, leading to logical errors or even out-of-bounds array access. The correct approach is to use strict inequality checks: `if (q.front() < i - k + 1). Additionally, when usingwhileto pop from the back, it is essential to check!q.empty()first; otherwise, callingback()` on an empty queue will result in Undefined Behavior (segmentation fault or infinite loop).
  2. Space Overhead and Index Misalignment Monotonic stacks and queues must store indices rather than the actual values. If values are mistakenly stored, lifespan checks cannot be performed (it won't be possible to determine whether the element has slid out of the window), and the next greater element's position cannot be precisely located. The size of the monotonic stack array must strictly match the size of the original sequence $N$. In NOIP/Linux environments, if using standard std::deque, its internal memory blocks are allocated in segments, which incurs a significant constant time overhead. In time-critical problems (such as processing $10^6$ data within 1.0s), it is advisable to use arrays to simulate double-ended queues (maintaining head and tail pointers) to achieve extreme O2 compilation optimization performance.

Classic NOIP/Luogu Real Problems

1. Luogu P2866 [USACO06NOV] Bad Hair Day S

2. Luogu P1419 Finding Paragraph

Original Source: local://1.5
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS