Chapter 3.5: Monotonic Stack & Monotonic Queue

📝 Before You Continue: Make sure you're comfortable with two pointers / sliding window (Chapter 3.4) and basic stack/queue operations (Chapter 3.1). This chapter builds directly on those techniques.

Monotonic stacks and queues are elegant tools that solve "nearest greater/smaller element" and "sliding window extremum" problems in O(N) time — problems that would naively require O(N²).

3.5.1 Monotonic Stack: Next Greater Element

Problem: Given an array A of N integers, for each element A[i], find the next greater element (NGE): the index of the first element to the right of i that is greater than A[i]. If none exists, output -1.

Naive approach: O(N²) — for each i, scan right until finding a greater element.

Monotonic stack approach: O(N) — maintain a stack that is always decreasing from bottom to top. When we push a new element, pop all smaller elements first (they just found their NGE!).

💡 Key Insight: The stack contains indices of elements that haven't found their NGE yet. When A[i] arrives, every element in the stack that is smaller than A[i] has found its NGE (it's i!). We pop them and record the answer.

单调栈状态变化示意（A=[2,1,5,6,2,3]）：

flowchart LR
    subgraph i0["i=0, A[0]=2"]
        direction TB
        ST0["Stack: [0]↓\n底→顶: [2]"]
    end
    subgraph i1["i=1, A[1]=1"]
        direction TB
        ST1["1<2, 直接入栈\nStack: [0,1]↓\n底→顶: [2,1]"]
    end
    subgraph i2["i=2, A[2]=5"]
        direction TB
        ST2["5>1: pop 1, NGE[1]=2\n5>2: pop 0, NGE[0]=2\nStack: [2]↓\n底→顶: [5]"]
    end
    subgraph i3["i=3, A[3]=6"]
        direction TB
        ST3["6>5: pop 2, NGE[2]=3\nStack: [3]↓\n底→顶: [6]"]
    end
    subgraph i5["i=5, A[5]=3"]
        direction TB
        ST5["3>2: pop 4, NGE[4]=5\n3<6, 入栈\nStack: [3,5]↓\n幕尾无 NGE"]
    end
    i0 --> i1 --> i2 --> i3 --> i5
    style ST2 fill:#dcfce7,stroke:#16a34a
    style ST3 fill:#dcfce7,stroke:#16a34a
    style ST5 fill:#dcfce7,stroke:#16a34a

💡 摘要： 栈始终保持单调递减（底大顶小）。每个元素至多入栈一次、出栈一次，总操作次数 O(2N) = O(N)。

Array A: [2, 1, 5, 6, 2, 3]
         idx: 0  1  2  3  4  5

Processing i=0 (A[0]=2): stack empty → push 0
Stack: [0]          // stack holds indices of unresolved elements

Processing i=1 (A[1]=1): A[1]=1 < A[0]=2 → just push
Stack: [0, 1]

Processing i=2 (A[2]=5): 
  A[2]=5 > A[1]=1 → pop 1, NGE[1] = 2  (A[2]=5 is next greater for A[1])
  A[2]=5 > A[0]=2 → pop 0, NGE[0] = 2  (A[2]=5 is next greater for A[0])
  Stack empty → push 2
Stack: [2]

Processing i=3 (A[3]=6): 
  A[3]=6 > A[2]=5 → pop 2, NGE[2] = 3
  Push 3
Stack: [3]

Processing i=4 (A[4]=2): A[4]=2 < A[3]=6 → just push
Stack: [3, 4]

Processing i=5 (A[5]=3): 
  A[5]=3 > A[4]=2 → pop 4, NGE[4] = 5
  A[5]=3 < A[3]=6 → stop, push 5
Stack: [3, 5]

End: remaining stack [3, 5] → NGE[3] = NGE[5] = -1 (no greater element to the right)

Result: NGE = [2, 2, 3, -1, 5, -1]
Verify: 
  A[0]=2, next greater is A[2]=5 ✓
  A[1]=1, next greater is A[2]=5 ✓
  A[2]=5, next greater is A[3]=6 ✓
  A[3]=6, no greater → -1 ✓

Complete Implementation

// Solution: Next Greater Element using Monotonic Stack — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int& x : A) cin >> x;

    vector<int> nge(n, -1);   // nge[i] = index of next greater element, -1 if none
    stack<int> st;             // monotonic decreasing stack (stores indices)

    for (int i = 0; i < n; i++) {
        // While the top of stack has a smaller value than A[i]
        // → the current element A[i] is the NGE of all those elements
        while (!st.empty() && A[st.top()] < A[i]) {
            nge[st.top()] = i;  // ← KEY: record NGE for stack top
            st.pop();
        }
        st.push(i);  // push current index (not yet resolved)
    }
    // Remaining elements in stack have no NGE → already initialized to -1

    for (int i = 0; i < n; i++) {
        cout << nge[i];
        if (i < n - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

Complexity Analysis:

• Each element is pushed exactly once and popped at most once
• Total operations: O(2N) = O(N)
• Space: O(N) for the stack

⚠️ Common Mistake: Storing values instead of indices in the stack. Always store indices — you need to know where in the array to record the answer.

3.5.2 Variations: Previous Smaller, Previous Greater

By changing the comparison direction and the traversal direction, you get four related problems:

Template for Previous Smaller Element:

// Previous Smaller Element: for each i, find the nearest j < i where A[j] < A[i]
vector<int> pse(n, -1);  // pse[i] = index of previous smaller, -1 if none
stack<int> st;

for (int i = 0; i < n; i++) {
    while (!st.empty() && A[st.top()] >= A[i]) {
        st.pop();  // pop elements that are >= A[i] (not the "previous smaller")
    }
    pse[i] = st.empty() ? -1 : st.top();  // stack top is the previous smaller
    st.push(i);
}

3.5.3 USACO Application: Largest Rectangle in Histogram

Problem: Given an array of heights H[0..N-1], find the area of the largest rectangle that fits under the histogram.

Key insight: For each bar i, the largest rectangle with height H[i] extends left and right until it hits a shorter bar. Use monotonic stack to find, for each i:

• left[i] = previous smaller element index
• right[i] = next smaller element index

直方图最大矩形边界计算示意（H=[2,1,5,6,2,3]）：

flowchart LR
    subgraph bars["每个柱子的左右边界"]
        direction TB
        B0["i=0, H=2\nleft=-1, right=1\nwidth=1, area=2"]
        B1["i=1, H=1\nleft=-1, right=6\nwidth=6, area=6"]
        B2["i=2, H=5\nleft=1, right=4\nwidth=2, area=10 ⭐"]
        B3["i=3, H=6\nleft=2, right=4\nwidth=1, area=6"]
        B4["i=4, H=2\nleft=1, right=6\nwidth=4, area=8"]
        B5["i=5, H=3\nleft=4, right=6\nwidth=1, area=3"]
    end
    note["最大面积 = 10\n（i=2, 高度=5, 宽度=2）"]
    style B2 fill:#dcfce7,stroke:#16a34a
    style note fill:#f0fdf4,stroke:#16a34a

💡 公式： width = right[i] - left[i] - 1，area = H[i] × width。左边界用"左侧第一个更小元素的下标"，右边界用"右侧第一个更小元素的下标"。

// Solution: Largest Rectangle in Histogram — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> H(n);
    for (int& h : H) cin >> h;

    // Find previous smaller for each position
    vector<int> left(n), right(n);
    stack<int> st;

    // Previous smaller (left boundary)
    for (int i = 0; i < n; i++) {
        while (!st.empty() && H[st.top()] >= H[i]) st.pop();
        left[i] = st.empty() ? -1 : st.top();  // index before rectangle starts
        st.push(i);
    }

    while (!st.empty()) st.pop();

    // Next smaller (right boundary)
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && H[st.top()] >= H[i]) st.pop();
        right[i] = st.empty() ? n : st.top();  // index after rectangle ends
        st.push(i);
    }

    // Compute maximum area
    long long maxArea = 0;
    for (int i = 0; i < n; i++) {
        long long width = right[i] - left[i] - 1;  // width of rectangle
        long long area = (long long)H[i] * width;
        maxArea = max(maxArea, area);
    }

    cout << maxArea << "\n";
    return 0;
}

Trace for H = [2, 1, 5, 6, 2, 3]:

left  = [-1, -1, 1, 2, 1, 4]   (index of previous smaller, -1 = none)
right = [1, 6, 4, 4, 6, 6]     (index of next smaller, n=6 = none)

Widths:  1-(-1)-1=1, 6-(-1)-1=6, 4-1-1=2, 4-2-1=1, 6-1-1=4, 6-4-1=1
Areas:   2×1=2, 1×6=6, 5×2=10, 6×1=6, 2×4=8, 3×1=3

Maximum area = 10
  i=2: H[2]=5, left[2]=1, right[2]=4, width=4-1-1=2, area=5×2=10 ✓
  (bars at indices 2 and 3 both have height ≥ 5, so the rectangle of height 5 spans width 2)

📌 Note for Students: Always trace through your algorithm on the sample input before submitting. Small off-by-one errors in index boundary calculations are the #1 source of bugs in monotonic stack problems.

3.5.4 Monotonic Deque: Sliding Window Maximum

Problem: Given array A of N integers and window size K, find the maximum value in each window of size K as it slides from left to right. Output N-K+1 values.

Naive approach: O(NK) — scan each window for its maximum.

Monotonic deque approach: O(N) — maintain a decreasing deque (front = maximum of current window).

💡 Key Insight: We want the maximum in a sliding window. We maintain a deque of indices such that:

1. The deque is decreasing in value (front is always the maximum)
2. The deque only contains indices within the current window

When a new element arrives:

• Remove all smaller elements from the back (they can never be the maximum while this new element is in the window)
• Remove the front if it's outside the current window

Step-by-Step Trace

Array A: [1, 3, -1, -3, 5, 3, 6, 7], K = 3

Window [1,3,-1]: max = 3
Window [3,-1,-3]: max = 3
Window [-1,-3,5]: max = 5
Window [-3,5,3]: max = 5
Window [5,3,6]: max = 6
Window [3,6,7]: max = 7

i=0, A[0]=1: deque=[0]
i=1, A[1]=3: 3>1 → pop 0; deque=[1]
i=2, A[2]=-1: -1<3 → push; deque=[1,2]; window [0..2]: max=A[1]=3 ✓
i=3, A[3]=-3: -3<-1 → push; deque=[1,2,3]; window [1..3]: front=1 still in window, max=A[1]=3 ✓
i=4, A[4]=5: 5>-3→pop 3; 5>-1→pop 2; 5>3→pop 1; deque=[4]; window [2..4]: max=A[4]=5 ✓
i=5, A[5]=3: 3<5→push; deque=[4,5]; window [3..5]: front=4 in window, max=A[4]=5 ✓
i=6, A[6]=6: 6>3→pop 5; 6>5→pop 4; deque=[6]; window [4..6]: max=A[6]=6 ✓
i=7, A[7]=7: 7>6→pop 6; deque=[7]; window [5..7]: max=A[7]=7 ✓

Complete Implementation

// Solution: Sliding Window Maximum using Monotonic Deque — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> A(n);
    for (int& x : A) cin >> x;

    deque<int> dq;   // monotonic decreasing deque, stores indices
    vector<int> result;

    for (int i = 0; i < n; i++) {
        // 1. Remove elements outside the current window
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();   // ← KEY: expired window front
        }

        // 2. Maintain decreasing property
        //    Remove from back all elements smaller than A[i]
        //    (they'll never be the max while A[i] is in the window)
        while (!dq.empty() && A[dq.back()] <= A[i]) {
            dq.pop_back();    // ← KEY: pop smaller elements from back
        }

        dq.push_back(i);   // add current element

        // 3. Record maximum once first full window is formed
        if (i >= k - 1) {
            result.push_back(A[dq.front()]);  // front = maximum of current window
        }
    }

    for (int i = 0; i < (int)result.size(); i++) {
        cout << result[i];
        if (i + 1 < (int)result.size()) cout << "\n";
    }
    cout << "\n";

    return 0;
}

Complexity:

• Each element is pushed/popped from the deque at most once → O(N) total
• Space: O(K) for the deque

⚠️ Common Mistake #1: Forgetting to check dq.front() <= i - k for window expiration. The deque must only contain indices in [i-k+1, i].

⚠️ Common Mistake #2: Using < instead of <= when popping from the back. With <, equal elements are preserved, but duplicates can cause issues. Use <= to maintain strict decreasing deque.

3.5.5 USACO Problem: Haybale Stacking (Monotonic Stack)

🔗 Inspiration: This problem type appears in USACO Bronze/Silver ("Haybale Stacking" style).

Problem: There are N positions on a number line. You have K operations: each operation sets all positions in [L, R] to 1. After all operations, output 1 for each position that was set, 0 otherwise.

Solution: Difference array (Chapter 3.2). But let's see a harder variant:

Harder Variant: Given an array H of N "heights," find for each position i the leftmost j such that H[j] < H[i] for all k in [j+1, i-1]. (Find the span of each bar in a histogram.)

This is exactly the "stock span problem" and solves using a monotonic stack — identical to the previous smaller element pattern.

// Stock Span Problem: for each day i, find how many consecutive days
// before i had price <= price[i]
// (the "span" of day i)
vector<int> stockSpan(vector<int>& prices) {
    int n = prices.size();
    vector<int> span(n, 1);
    stack<int> st;  // monotonic decreasing stack of indices

    for (int i = 0; i < n; i++) {
        while (!st.empty() && prices[st.top()] <= prices[i]) {
            st.pop();
        }
        span[i] = st.empty() ? (i + 1) : (i - st.top());
        st.push(i);
    }
    return span;
}
// span[i] = number of consecutive days up to and including i with price <= prices[i]

3.5.6 USACO-Style Problem: Barn Painting Temperatures

Problem: N readings, find the maximum value in each window of size K.

(This is the sliding window maximum — solution already shown in 3.5.4.)

A trickier USACO variant: Given N cows in a line, each with temperature T[i]. A "fever cluster" is a maximal contiguous subarray where all temperatures are above threshold X. Find the maximum cluster size for each of Q threshold queries.

Offline approach: Sort queries by X, process with monotonic deque.

⚠️ Common Mistakes in Chapter 3.5

1. Storing values instead of indices — Always store indices. You need them to check window bounds and to record answers.

2. Wrong comparison in deque (< vs <=) — For sliding window MAXIMUM, pop when A[dq.back()] <= A[i] (strict non-increase). For MINIMUM, pop when A[dq.back()] >= A[i].

3. Forgetting window expiration — In sliding window deque, always check dq.front() < i - k + 1 (or <= i - k) before recording the maximum.

4. Stack bottom-top direction confusion — The "monotonic" property means: bottom-to-top, the stack is increasing (for NGE) or decreasing (for NSE). Draw it out if confused.

5. Processing order for NGE vs PSE:

   • Next Greater Element: left-to-right traversal
   • Previous Greater Element: right-to-left traversal (OR: left-to-right, record stack.top() before pushing)

Chapter Summary

📌 Key Summary

🧩 Template Quick Reference

// Monotone decreasing stack (for NGE / Next Greater Element)
stack<int> st;
for (int i = 0; i < n; i++) {
    while (!st.empty() && A[st.top()] < A[i]) {
        answer[st.top()] = i;  // i is the NGE of st.top()
        st.pop();
    }
    st.push(i);
}

// Monotone decreasing deque (sliding window maximum)
deque<int> dq;
for (int i = 0; i < n; i++) {
    while (!dq.empty() && dq.front() <= i - k) dq.pop_front();  // remove expired
    while (!dq.empty() && A[dq.back()] <= A[i]) dq.pop_back();  // maintain monotone
    dq.push_back(i);
    if (i >= k - 1) ans.push_back(A[dq.front()]);
}

❓ FAQ

Q1: Should the monotone stack store values or indices?

A: Always store indices. Even if you only need values, storing indices is more flexible — you can get the value via A[idx], but not vice versa. Especially when computing widths (e.g., histogram problems), indices are required.

Q2: How do I decide between monotone stack and two pointers?

A: Look at the problem structure — if you need "for each element, find the first greater/smaller element to its left/right", use monotone stack. If you need "maintain the maximum of a sliding window", use monotone deque. If "two pointers moving toward each other from both ends", use two pointers.

Q3: Why is the time complexity of monotone stack O(N) and not O(N²)?

A: Amortized analysis. Each element is pushed at most once and popped at most once, totaling 2N operations, so O(N). Although a single while loop may pop multiple times, the total number of pops across all while loops never exceeds N.

Practice Problems

Problem 3.5.1 — Next Greater Element 🟢 Easy For each element in an array, find the first element to its right that is greater. Print -1 if none exists.

Problem 3.5.2 — Daily Temperatures 🟢 Easy For each day, find how many days you have to wait until a warmer temperature. (LeetCode 739 style)

Problem 3.5.3 — Sliding Window Maximum 🟡 Medium Find the maximum in each sliding window of size K.

Problem 3.5.4 — Largest Rectangle in Histogram 🟡 Medium Find the largest rectangle that fits in a histogram.

Problem 3.5.5 — Trapping Rain Water 🔴 Hard Given an elevation map, compute how much water can be trapped after raining. (Classic problem)

🏆 Challenge: USACO 2016 February Silver: Fencing the Cows Given a polygon, find if a point is inside. Use ray casting — involves careful implementation with edge cases.