Monotonic Stack

A monotonic stack keeps only the unresolved elements and evicts anything they can already answer. That one rule turns repeated left-to-right scans into a single $O(n)$ pass for next-greater, next-smaller, histogram, stock-span, and contribution-counting problems.

Difficulty: Intermediate | Prerequisites: Stack, Queue, and Deque | CF Rating Range: 1200–2200

Intuition

You have an array a = [4, 3, 2, 5, 1, 6] and you need the next greater element (NGE) for each position—the first value to its right that is strictly larger.

The obvious approach is to scan rightward from every index until you find something bigger.

i=0  a[i]=4 : compare 3(no), 2(no), 5(yes!) -> nge = 5    3 comparisons
i=1  a[i]=3 : compare 2(no), 5(yes!)        -> nge = 5    2 comparisons
i=2  a[i]=2 : compare 5(yes!)               -> nge = 5    1 comparison
i=3  a[i]=5 : compare 1(no), 6(yes!)        -> nge = 6    2 comparisons
i=4  a[i]=1 : compare 6(yes!)               -> nge = 6    1 comparison
i=5  a[i]=6 : nothing to scan               -> nge = -1   0 comparisons
-------------------------------------------------------------
                                               Total:  9 comparisons

Result: nge = [5, 5, 5, 6, 6, -1]. Nine comparisons for six elements—that does not sound terrible. But look at the pattern of wasted work:

• Index 0 scans past 3 and 2 before finding 5. Those two comparisons are pure waste—3 and 2 are smaller than 4, so they could never be its answer.
• Index 1 scans past 2 (also useless) before finding 5.
• Index 2 finally checks 5—the same 5 that indices 0 and 1 already plowed through.

Three indices all trudge through the same declining stretch [3, 2] only to arrive at the same answer. Now imagine a fully descending array of length $n$: every index scans all the way to the end, totaling $n+(n-1)+\dots +1=\frac{n(n-1)}{2}$ comparisons. At $n={10}^5$, that is roughly $5\times {10}^9$ operations—far too slow for a 1-second time limit.

The waste is not subtle: the same small candidates get checked again and again. There has to be a better way.

The right question is not "how do I search faster?" but "when does an element stop being useful?" Once a new value makes earlier values irrelevant, pop them immediately, record the answer, and keep only the unresolved elements in a stack ordered from large (bottom) to small (top).

Real-world analogy. Picture a line of people waiting for someone taller to tap them on the shoulder. Short people stand behind tall people. When a tall newcomer arrives, every shorter person in front of them exclaims "That's the one!" and leaves. Only those still taller than the newcomer stay in line, still waiting. The line always looks sorted from tallest (front) to shortest (back)—which is exactly the decreasing stack.

Where the analogy breaks. In a physical line, people leaving creates gaps and shifting. In the stack, popping is instant and free—there is no rearranging. The stack's last-in-first-out discipline makes the bookkeeping perfectly clean: you only ever compare against the top.

Trace: [4, 3, 2, 5, 1, 6]

Trace the algorithm on the same array a = [4, 3, 2, 5, 1, 6]. The stack stores indices, because the index is what lets us write the answer for an earlier element and safely refer back to it later.

Step 1: Process a[0]=4.  Stack empty -- push index 0.

  a[]:  4   3   2   5   1   6
        ^
       i=0

  stk:  +---+
        | 4 |  <-- top              (1 push, 0 pops)
        +---+

  nge:  [ .   .   .   .   .   . ]


Step 2: Process a[1]=3.  3 < 4 (top) -- no pop.  Push index 1.

  a[]:  4   3   2   5   1   6
            ^
           i=1

  stk:  +---+
        | 3 |  <-- top              (1 push, 0 pops)
        | 4 |
        +---+

  nge:  [ .   .   .   .   .   . ]


Step 3: Process a[2]=2.  2 < 3 (top) -- no pop.  Push index 2.

  a[]:  4   3   2   5   1   6
                ^
               i=2

  stk:  +---+
        | 2 |  <-- top              (1 push, 0 pops)
        | 3 |
        | 4 |
        +---+

  nge:  [ .   .   .   .   .   . ]

  Stack is now [4, 3, 2] -- three unresolved elements,
  values decreasing from bottom to top.


Step 4: Process a[3]=5.  *** the big sweep ***
        5 > 2 (top) -> pop index 2, record nge[2] = 5
        5 > 3 (top) -> pop index 1, record nge[1] = 5
        5 > 4 (top) -> pop index 0, record nge[0] = 5
        Stack empty.  Push index 3.

  a[]:  4   3   2   5   1   6
                    ^
                   i=3

  stk:  +---+
        | 5 |  <-- top              (1 push, 3 pops)
        +---+

  nge:  [ 5   5   5   .   .   . ]
          *   *   *
  Three elements resolved in one sweep!


Step 5: Process a[4]=1.  1 < 5 (top) -- no pop.  Push index 4.

  a[]:  4   3   2   5   1   6
                        ^
                       i=4

  stk:  +---+
        | 1 |  <-- top              (1 push, 0 pops)
        | 5 |
        +---+

  nge:  [ 5   5   5   .   .   . ]


Step 6: Process a[5]=6.
        6 > 1 (top) -> pop index 4, record nge[4] = 6
        6 > 5 (top) -> pop index 3, record nge[3] = 6
        Stack empty.  Push index 5.

  a[]:  4   3   2   5   1   6
                            ^
                           i=5

  stk:  +---+
        | 6 |  <-- top              (1 push, 2 pops)
        +---+

  nge:  [ 5   5   5   6   6   . ]


End: Index 5 remains on the stack -- nge[5] = -1.

Final result:  nge = [5, 5, 5, 6, 6, -1]

6 pushes + 5 pops = 11 stack operations, each $O(1)$. Brute force did 9 element comparisons on this small input; on a descending array of length $\mathrm{1,000}$ it would do $\sim \mathrm{500,000}$ while the stack still does at most $\mathrm{2,000}$. The gap is $O(n^2)$ vs. $O(n)$.

The Invariant

+------------------------------------------------------------------+
| The stack contains exactly the indices whose NGE is still        |
| unknown, and their values form a non-increasing sequence from    |
| bottom to top:                                                   |
|                                                                  |
|   a[stk[0]] >= a[stk[1]] >= ... >= a[stk[top]]                  |
|                                                                  |
| Before pushing index i, pop every index j on top where          |
| a[j] < a[i]. Each pop (1) preserves the ordering and            |
| (2) records a[i] as the NGE for the popped index.                |
+------------------------------------------------------------------+

Why it holds. An element stays on the stack exactly as long as it has no answer. The moment something greater arrives, it gets popped and its NGE is recorded. Since we pop everything smaller than the newcomer, whatever survives below is at least as large—so the non-increasing order is restored before the push.

Connect to the walkthrough. Look at Step 4 above—when 5 arrives, the stack holds [4, 3, 2] (decreasing). All three are smaller than 5, so all three pop. If we skipped the pops and just pushed 5 on top of 2, the stack would read [4, 3, 2, 5]—increasing at the top, violating the invariant. The pops are not bookkeeping overhead; they are the answers.

Amortized $O(n)$. Each of the $n$ elements is pushed exactly once and popped at most once—at most $2n$ stack operations total, regardless of how many pops a single push triggers. Step 4 popped three elements in one go, but those three can never be popped again. The total across all steps stays $\le 2n$.

With the invariant clear, the code is mechanical. The only judgment left is choosing the comparison direction—which boils down to deciding when a candidate becomes irrelevant.

The question before you code: "When does an element become irrelevant?"

Every monotonic stack problem boils down to one question: what event makes a stacked element no longer worth keeping? For NGE, an element becomes irrelevant the moment something greater arrives—it has been "resolved." For the histogram, a bar becomes irrelevant when a shorter bar arrives—the tall bar can no longer extend rightward. Identify the irrelevance condition first; the code writes itself after that.

The stack is a waiting list of open questions.

Don't think of the stack as "a data structure I'm using for efficiency." Every element on it has an open question—"what is my next greater element?"—that hasn't been answered yet. A push means "I have a new open question." A pop means "question answered." When the loop ends, anything still on the stack never got an answer—those are your $-1$ entries.

The pop condition (> vs >=) is the critical detail for duplicates.

This single character determines whether equal elements resolve each other or coexist on the stack. Getting it wrong doesn't crash—it silently produces wrong answers that are off by one position.

Array: [2, 5, 5, 3]

  Pop with STRICT comparison:  a[stk.back()] < a[i]
  ---------------------------------------------------------
  i=0  val=2   stk: [2]          Push 2
  i=1  val=5   stk: [5]          Pop 2 (2<5, yes), push 5
  i=2  val=5   stk: [5, 5]       5<5? NO -> push.  Both 5s COEXIST.
  i=3  val=3   stk: [5, 5, 3]    5<3? NO -> push.

  nge = [5, -1, -1, -1]
              ^    ^
      Neither 5 resolves the other -- equal is NOT "strictly greater."


  Pop with NON-STRICT comparison:  a[stk.back()] <= a[i]
  ---------------------------------------------------------
  i=0  val=2   stk: [2]          Push 2
  i=1  val=5   stk: [5]          Pop 2 (2<=5, yes), push 5
  i=2  val=5   stk: [5]          Pop 5 (5<=5, yes), push 5.  First 5 RESOLVED.
  i=3  val=3   stk: [5, 3]       5<=3? NO -> push.

  nge = [5, 5, -1, -1]
             ^
     First 5 is resolved by the equal second 5 -- "next greater or equal."

Before coding, decide explicitly: does "greater" mean strict > or $\ge$? Then pick the comparison to match.

std::stack and the vector Alternative

A single push may trigger $k$ pops, which looks expensive. But those $k$ elements were each pushed exactly once and are now popped for the last time—they will never be touched again. Total work across all pushes: at most $n$ pushes + $n$ pops = $2n$ operations. That is why a single step can be $O(n)$ worst-case without the overall algorithm being $O(n^2)$.

Operation (on vector<int> used as a stack)	Method	Time
Push	stk.push_back(i)	$O(1)$
Top	stk.back()	$O(1)$
Pop	stk.pop_back()	$O(1)$
Empty?	stk.empty()	$O(1)$

Every trigger phrase below is a different surface form of the same question: "can I discard older candidates the moment a better one arrives?"

Trigger phrases—if you see any of these in a problem statement, reach for a monotonic stack:

1. "next greater element" or "next smaller element"
2. "for each element, find the nearest element to the left/right satisfying a comparison"
3. "largest rectangle in histogram" or skyline / building variants
4. "sum of subarray minimums" or "sum of subarray maximums" (contribution counting)
5. "stock span"—count consecutive preceding days with price $\le$ today

Counter-examples—problems that look like monotonic stack but are not:

1. "Sliding window maximum over a fixed window of size $k$." You need elements to expire from both ends as the window slides, so you need a monotonic deque, not a stack. See 05-monotonic-queue.md.
2. "Find the $k$-th largest element." Monotonic stack gives nearest-neighbor relationships, not global ranking. Use a heap or quickselect.
3. "Answer range minimum queries with updates." Monotonic stack is a one-pass offline technique. Repeated online queries with modifications need a segment tree, not a stack.

---

C++ STL Reference

Monotonic stack is a pattern built on std::stack (or a plain vector used as a stack).

Function / Class	Header	What it does	Time Complexity
stack<T>	<stack>	LIFO container adaptor	--
s.push(x)	--	Push element onto top	$O(1)$
s.top()	--	Access top element (no removal)	$O(1)$
s.pop()	--	Remove top element	$O(1)$
s.empty()	--	Check if stack is empty	$O(1)$
s.size()	--	Number of elements	$O(1)$

Contest tip: Most competitive programmers skip std::stack and use vector<int> with push_back / back / pop_back. It is faster (no adaptor layer) and gives random access when you need it.

---

Implementation

Canonical Problem: Next Greater Element

Given a[0..n-1], for each index i find the smallest j > i such that a[j] > a[i]. Output a[j], or -1 if none exists.

Minimal Contest Template

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    vector<int> nge(n, -1);
    vector<int> stk;
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && a[stk.back()] < a[i]) {
            nge[stk.back()] = a[i];
            stk.pop_back();
        }
        stk.push_back(i);
    }

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

Explained Version

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // nge[i] = -1 means no greater element exists to the right
    vector<int> nge(n, -1);

    // Stack of indices. Invariant: a[stk[0]] >= a[stk[1]] >= ... >= a[stk.back()]
    // (decreasing). Each index on the stack is "unresolved" -- still waiting for
    // something greater to appear to its right.
    vector<int> stk;

    for (int i = 0; i < n; i++) {
        // a[i] is a candidate NGE for every stack element it exceeds.
        // Pop all smaller elements -- a[i] IS their next greater element.
        while (!stk.empty() && a[stk.back()] < a[i]) {
            nge[stk.back()] = a[i];
            stk.pop_back();
        }
        stk.push_back(i);
    }
    // Anything still on the stack has no next greater element -- nge already -1.

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

Variant: Next Smaller Element

For each i, find the smallest j > i with a[j] < a[i]. Flip the direction: the stack is now increasing (values increase bottom-to-top) and pops when the newcomer is smaller.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // nse[i] = index of the next smaller element, or -1
    vector<int> nse(n, -1);

    // Increasing stack: a[stk[0]] <= a[stk[1]] <= ... <= a[stk.back()]
    // Pop when a[i] is SMALLER than the top -- the stack "fears" smaller arrivals.
    vector<int> stk;

    for (int i = 0; i < n; i++) {
        while (!stk.empty() && a[stk.back()] > a[i]) {
            nse[stk.back()] = i;
            stk.pop_back();
        }
        stk.push_back(i);
    }
}

On a = [4, 3, 2, 5, 1, 6]:

i=0 a[i]=4  stk: [0(4)]                       Push
i=1 a[i]=3  Pop 0(4>3), nse[0]=1.  stk:[1(3)] Push
i=2 a[i]=2  Pop 1(3>2), nse[1]=2.  stk:[2(2)] Push
i=3 a[i]=5  5>2, no pop.  stk:[2(2), 3(5)]    Push
i=4 a[i]=1  Pop 3(5>1), nse[3]=4.
             Pop 2(2>1), nse[2]=4.  stk:[4(1)] Push
i=5 a[i]=6  6>1, no pop.  stk:[4(1), 5(6)]    Push
End: nse[4]=-1, nse[5]=-1

Result: nse = [1, 2, 4, 4, -1, -1]

Previous Smaller Element

The mirror of NSE: read the answer before pushing instead of recording on pop. This pattern appears constantly in histogram-style problems.

vector<int> pse(n, -1);
vector<int> stk;
for (int i = 0; i < n; i++) {
    while (!stk.empty() && a[stk.back()] >= a[i])
        stk.pop_back();
    if (!stk.empty()) pse[i] = stk.back();
    stk.push_back(i);
}

Largest Rectangle in Histogram

For each bar, find how far it extends left and right as the minimum height. Equivalently, compute PSE and NSE for each bar; the rectangle with bar i as its min has area $h_i\times (\text{nse}[i]-\text{pse}[i]-1)$. The single-pass version folds both into one increasing stack and computes area on every pop.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (auto& x : h) cin >> x;

    long long ans = 0;
    vector<int> stk;  // increasing stack of indices

    // i goes up to n: when i == n, treat height as 0 — a virtual sentinel
    // shorter than every real bar, forcing all remaining bars to pop.
    for (int i = 0; i <= n; i++) {
        int cur = (i == n) ? 0 : h[i];
        while (!stk.empty() && h[stk.back()] >= cur) {
            int ht = h[stk.back()];
            stk.pop_back();
            // Width: (previous stack top + 1) through (i - 1), inclusive
            int w = stk.empty() ? i : i - stk.back() - 1;
            ans = max(ans, (long long)ht * w);
        }
        if (i < n) stk.push_back(i);  // don't push the sentinel
    }

    cout << ans << "\n";
}

Why i - stk.back() - 1? After popping bar j, the new stack top t is the nearest bar to the left that is shorter than h[j]. Bar i is the nearest shorter bar to the right. So bar j spans t+1 through i-1, giving width i - t - 1. If the stack is empty after the pop, j extends all the way to the left edge—width i.

heights = [2, 1, 5, 6, 2, 3]

            ┌───┐
        ┌───┤   │
        │   │   │           ┌───┐
┌───┐   │   │   ├───┐   │   │   │
│ 2 │ 1 │ 5 │ 6 │ 2 │ 3 │
└───┴───┴───┴───┴───┴───┘
  0   1   2   3   4   5

Operation	Time (per call)	Amortized over $n$ elements	Space
Push onto monotonic stack	$O(1)$ best, $O(n)$ worst	$O(1)$ amortized	$O(n)$ total
Pop (triggered by push)	$O(1)$	--	--
Full NGE / NSE pass	--	$O(n)$ total	$O(n)$
Largest rectangle in histogram	--	$O(n)$ total	$O(n)$

i=0, cur=2:  empty, push 0.              stk=[0]       heights:[2]
i=1, cur=1:  h[0]=2 >= 1 → pop 0.
               ht=2, stack empty → w=i=1, area=2×1=2.
             Push 1.                      stk=[1]       heights:[1]
i=2, cur=5:  1 < 5, no pop. push 2.       stk=[1,2]     heights:[1,5]
i=3, cur=6:  5 < 6, no pop. push 3.       stk=[1,2,3]   heights:[1,5,6]
i=4, cur=2:  h[3]=6 >= 2 → pop 3.
               ht=6, new top=2, w=4-2-1=1, area=6×1=6.
             h[2]=5 >= 2 → pop 2.
               ht=5, new top=1, w=4-1-1=2, area=5×2=10.  ← max!
             h[1]=1 < 2, stop. push 4.    stk=[1,4]     heights:[1,2]
i=5, cur=3:  2 < 3, no pop. push 5.       stk=[1,4,5]   heights:[1,2,3]
i=6 (sentinel, cur=0):
             h[5]=3 >= 0 → pop 5.
               ht=3, new top=4, w=6-4-1=1, area=3×1=3.
             h[4]=2 >= 0 → pop 4.
               ht=2, new top=1, w=6-1-1=4, area=2×4=8.
             h[1]=1 >= 0 → pop 1.
               ht=1, stack empty → w=i=6, area=1×6=6.

Final answer: 10 (bar h=5 at index 2 extending over indices 2..3)

Problem Patterns

Next / Previous Greater or Smaller. The base pattern. Four variants share one template—forward loop for "next," backward for "previous," flip the comparison for smaller vs. greater.

CSES 1645—Nearest Smaller Values. Direct PSE application. CF 1691D—Max GEQ Sum (1800). Stack finds the range each element dominates as the max; verify with prefix sums.

Largest Rectangle / Histogram Variants. Single-pass increasing stack with a virtual sentinel at the right end.

Previous Smaller Element (PSE) / Previous Greater Element (PGE)

Process left to right; the stack holds candidates. After popping violators, whatever survives on top is the previous smaller (or greater) element for the current index.

vector<int> pse(n, -1);
vector<int> stk;
for (int i = 0; i < n; i++) {
    while (!stk.empty() && a[stk.back()] >= a[i])
        stk.pop_back();
    if (!stk.empty()) pse[i] = stk.back();
    stk.push_back(i);
}

CSES 1645—Nearest Smaller Values. Direct PSE application.

Largest Rectangle in Histogram

For each bar, find how far it extends left and right as the minimum height. Compute PSE and NSE for each bar; the area of the rectangle with bar $i$ as its minimum height is $h_i\times (\text{nse}[i]-\text{pse}[i]-1)$.

The single-pass version pushes bars onto an increasing stack and computes area on every pop, when a shorter bar arrives.

long long largestRect(vector<int>& h) {
    int n = h.size();
    long long ans = 0;
    vector<int> stk;
    for (int i = 0; i <= n; i++) {
        while (!stk.empty() && (i == n || h[stk.back()] >= h[i])) {
            int ht = h[stk.back()]; stk.pop_back();
            int w = stk.empty() ? i : i - stk.back() - 1;
            ans = max(ans, (long long)ht * w);
        }
        stk.push_back(i);
    }
    return ans;
}

  Histogram:  heights = [2, 1, 5, 6, 2, 3]

  Bar chart:
              +---+
          +---+   |
          |   |   |           +---+
  +---+   |   |   +---+   |   |
  |   |   |   |   |   |   |   |
  | 2 | 1 | 5 | 6 | 2 | 3 |
  +---+---+---+---+---+---+
    0   1   2   3   4   5

  Increasing stack -- pop when a shorter bar arrives.
  Stack stores indices; heights shown for clarity.

  i=0  h=2  stk: [(0,h=2)]                          Push
  i=1  h=1  Pop (0,h=2): w=1, area=2*1=2             Push(1)
             stk: [(1,h=1)]
  i=2  h=5  stk: [(1,h=1),(2,h=5)]                  Push
  i=3  h=6  stk: [(1,h=1),(2,h=5),(3,h=6)]          Push
  i=4  h=2  Pop (3,h=6): w=4-2-1=1, area=6*1= 6
             Pop (2,h=5): w=4-1-1=2, area=5*2=10  <-- max so far!
             stk: [(1,h=1),(4,h=2)]                  Push
  i=5  h=3  stk: [(1,h=1),(4,h=2),(5,h=3)]          Push
  End:       Pop (5,h=3): w=6-4-1=1, area=3*1= 3
             Pop (4,h=2): w=6-1-1=4, area=2*4= 8
             Pop (1,h=1): w=6       , area=1*6= 6  (stack empty -> w=i)

  Answer: 10  (bar h=5 extending over indices 2..3)

  Key insight: the stack remembers left boundaries implicitly.
  Width on pop = i - stk.back() - 1  (or i if stack empty after pop).

Detailed step-by-step stack trace for heights = [2, 1, 5, 6, 2, 3]:

i=0, cur=2:
  Stack is empty, push 0.
  stk = [0]                  heights on stack: [2]

i=1, cur=1:
  h[0]=2 >= 1 -> POP index 0.
    ht=2, stack now empty -> w = i = 1.
    area = 2 * 1 = 2.  ans = 2
  Push 1.
  stk = [1]                  heights on stack: [1]

i=2, cur=5:
  h[1]=1 < 5, no pop.  Push 2.
  stk = [1, 2]               heights on stack: [1, 5]

i=3, cur=6:
  h[2]=5 < 6, no pop.  Push 3.
  stk = [1, 2, 3]            heights on stack: [1, 5, 6]

i=4, cur=2:
  h[3]=6 >= 2 -> POP index 3.
    ht=6, new top=2. w = 4 - 2 - 1 = 1.
    area = 6 * 1 = 6.  ans = 6
  h[2]=5 >= 2 -> POP index 2.
    ht=5, new top=1. w = 4 - 1 - 1 = 2.
    area = 5 * 2 = 10. ans = 10    <-- new maximum!
  h[1]=1 < 2, stop.  Push 4.
  stk = [1, 4]               heights on stack: [1, 2]

i=5, cur=3:
  h[4]=2 < 3, no pop.  Push 5.
  stk = [1, 4, 5]            heights on stack: [1, 2, 3]

i=6 (sentinel, cur=0):       <-- virtual bar forces all pops
  h[5]=3 >= 0 -> POP index 5.
    ht=3, new top=4. w = 6 - 4 - 1 = 1.
    area = 3 * 1 = 3.  ans = 10
  h[4]=2 >= 0 -> POP index 4.
    ht=2, new top=1. w = 6 - 1 - 1 = 4.
    area = 2 * 4 = 8.  ans = 10
  h[1]=1 >= 0 -> POP index 1.
    ht=1, stack now empty -> w = 6.
    area = 1 * 6 = 6.  ans = 10
  stk = []

Final answer: 10
  The 5-tall bar (index 2) extends over indices 2..3 (width 2).
  Rectangle:     +---+---+
                 |   |   |
                 | 5 | 6 |     5 * 2 = 10
                 |   |   |
                 +---+---+

CSES 1142—Advertisement. Direct histogram problem. CF 1313C2—Skyscrapers, Hard Version (1900). Histogram-flavored: maximize total height under unimodal constraint.

Stock Span

For each day, count how many consecutive preceding days had price $\le$ today. Maintain a decreasing stack of indices; when you push index $i$, the span is i - stk.back() (or i + 1 if the stack is empty after popping).

Appears as a subproblem in various CF problems. A staple interview question for training the monotonic stack reflex.

Sum of Subarray Minimums / Maximums

To compute $\sum _{\text{all subarrays}}min(\text{subarray})$, count for each $a[i]$ how many subarrays have $a[i]$ as their minimum, using PSE and NSE:

$$\text{contribution}(i)=a[i]\times (i-\text{pse}[i])\times (\text{nse}[i]-i)$$

Duplicate trap: use strict < on one side and non-strict <= on the other, otherwise each subarray's min gets counted twice when equal elements exist.

CF 817D—Imbalanced Array (1900). Compute $\sum (max-min)$ over all subarrays = $\sum max-\sum min$, each via monotonic stack.

Max Subarray Sum Minus Max Element

Fix the max element; use its dominance range (from PSE + NSE) to bound the subarray, then optimize sum within.

CF 1359D—Yet Another Yet Another Task (2000). Fix the max element, optimize sum minus that max over its dominance range.

Monotonic Stack + DP

Use PSE/NSE to find valid transitions, then run DP over them. This pattern is common in jump and path problems where valid moves are defined by height comparisons.

CF 1407D—Discrete Centrifugal Jumps (2200). Monotonic stack finds valid jump targets; DP computes shortest path.

Circular arrays. If "next greater" wraps around the end, process i = 0 .. 2n-1 using a[i % n]. The first pass may leave elements unresolved; the second pass wraps around to finish them. Don't record answers for indices from the second pass—nge[] stays of size $n$.

When Not to Use

• Sliding window min/max over a fixed window $k$. Elements must expire from both ends—use a monotonic deque, not a stack. See Monotonic Queue.
• $k$-th largest element. Monotonic stack gives nearest-neighbor relationships, not global ranking. Use a heap or quickselect.
• Range queries with updates. Monotonic stack is one-pass and offline. For online queries with modifications, use a Segment Tree.
• Range min/max with arbitrary endpoints. Use a Sparse Table or segment tree.

Common Mistakes & Debugging

Off-by-one on widths. In the histogram, the width for a popped index j with new stack top t and current i is i - t - 1, not i - j. If the stack is empty after popping, the width is i. Draw a 3-bar example when unsure.

Increasing vs. decreasing—which one?

• Decreasing stack (values decrease bottom-to-top): pops on a larger arrival. Use for NGE / PGE.
• Increasing stack (values increase bottom-to-top): pops on a smaller arrival. Use for NSE / PSE.

Mnemonic: the stack "fears" what you are searching for. Looking for the next greater? Stack is decreasing—it panics and pops when something greater shows up.

Pushing values instead of indices. stk.push_back(a[i]) looks fine until you try to write nge[stk.back()] = ... and realize you just lost every positional reference. Always stk.push_back(i).

Equal elements: < vs <= changes the answer.

• For "next greater": use <= to pop (equal elements are NOT greater, so they stay).
• For "next greater or equal": use < to pop (equal elements ARE valid, so they trigger pop).

Getting this wrong silently produces off-by-one answers. Before coding, explicitly decide: does "greater" mean strictly greater or $\ge$? Then choose the comparison accordingly.

  Example -- array: [3, 1, 3, 2]

  "Next strictly greater" for index 0 (value 3):
  - Index 2 has value 3 -- NOT strictly greater, skip
  - Answer: -1 (no strictly greater element to the right)

  "Next greater or equal" for index 0 (value 3):
  - Index 2 has value 3 -- IS >= 3, match
  - Answer: index 2

Forgetting the cleanup pass. After the main loop, the stack may still hold indices. For NGE these get $-1$. For the histogram you must pop them all—the standard trick is to iterate i up to n (not n-1) and treat h[n] as $0$. Missing this is the most common bug.

Cleanup pass—two methods:

// Explicit cleanup
while (!stk.empty()) {
    nge[stk.back()] = -1;
    stk.pop_back();
}

// Method 2: Virtual sentinel -- extend the loop by one iteration.
// Treat a[n] as a value larger than any real element (for NGE)
// or smaller than any real element (for histogram).
// This forces all remaining elements to pop inside the loop itself.
for (int i = 0; i <= n; i++) {       // note: i goes to n, not n-1
    int cur = (i == n) ? INT_MAX : a[i];  // virtual sentinel for NGE
    while (!stk.empty() && a[stk.back()] < cur) {
        nge[stk.back()] = (i == n) ? -1 : a[i];
        stk.pop_back();
    }
    if (i < n) stk.push_back(i);
}

The virtual sentinel approach is cleaner because it handles cleanup inside the same loop—no separate post-loop code, fewer chances for bugs.

Storing values instead of indices. Always store indices on the stack. You can recover values via a[stk.back()], but you cannot recover indices from values. You need indices to compute widths, set answer arrays, and handle duplicates.

Clearing the stack between test cases. In multi-test problems, forgetting stk.clear() carries stale indices into the next test case. Declare the stack inside the per-test loop or clear it explicitly.

Mental Traps

Trap 1: "Monotonic stack is just an optimization trick."

It is not an optimization layered on top of brute force—it is a structural observation about which elements remain relevant. In brute-force NGE, you scan rightward past elements that can never be anyone's answer. The monotonic stack doesn't "speed up" that scan; it eliminates the irrelevant elements entirely by recognizing that a small element hiding behind a larger one will never be seen again.

The stack is not "brute force made faster." It is a completely different framing—instead of asking "for this element, where is the answer?" you ask "for this new arrival, whose answer am I?"

Trap 2: "I need to figure out what to push onto the stack."

You always push the current index. Every single iteration ends with a push. The real question is not "what to push" but "what invariant do I maintain before pushing?"—because the invariant determines the pop condition, and the pop condition determines what problem you are solving.

  The decision tree is short:

  +-- What am I looking for?
  |
  +-- Next GREATER element  ->  Decreasing stack  ->  pop while a[top] <  a[i]
  +-- Next SMALLER element  ->  Increasing stack  ->  pop while a[top] >  a[i]
  +-- Next GREATER OR EQUAL ->  Decreasing stack  ->  pop while a[top] <= a[i]
  +-- Next SMALLER OR EQUAL ->  Increasing stack  ->  pop while a[top] >= a[i]

  After choosing: push i.  Always.

Resolved vs. unresolved—a step-by-step view:

The following trace shows exactly when each element's question gets answered. Elements on the stack are unresolved (still waiting); popped elements are resolved (answer found).

  Array: [4, 7, 3, 5, 2, 6]       Task: Next Greater Element

  Step   Current   Stack (bottom->top)     Resolved this step
  ----   -------   ------------------     ---------------------
   1      4        [4]                    --
   2      7        [7]                    4 -> 7  (7 answers 4's question)
   3      3        [7, 3]                 --
   4      5        [7, 5]                 3 -> 5  (5 answers 3's question)
   5      2        [7, 5, 2]              --
   6      6        [7, 6]                 2 -> 6, 5 -> 6  (6 answers both)
  end     --       [7, 6] remain          7 -> -1, 6 -> -1  (never resolved)

  Observation: an element sits on the stack from arrival until something
  greater resolves it.  Stack = waiting list of unresolved elements.
  Elements left at the end have no answer -> -1.

---

Self-Test

Cover the page and answer each of these before moving to practice problems:

• [ ] Given an array, can you trace the monotonic stack state at each step and identify which elements get popped and why?
• [ ] Can you explain why the amortized time complexity is $O(n)$ even though a single push may trigger $O(n)$ pops?
• [ ] If asked to find "next greater or equal" instead of "next strictly greater," which single character in the pop condition changes, and why?
• [ ] For "sum of subarray minimums" with duplicates, why must you use strict comparison on one side and non-strict on the other?
• [ ] In the histogram problem, when you pop index j with current index i and stack top t, why is the width i - t - 1 and not i - j?
• [ ] Can you identify the monotonic stack pattern in a new problem without being told? What trigger phrases do you look for?
• [ ] What is the difference between "the stack is an optimization" and "the stack tracks unresolved elements"? Why does the second framing help you write correct code?

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Nearest Smaller Values	CSES	Easy	Direct PSE—one monotonic stack pass
2	Advertisement	CSES	Easy	Largest rectangle in histogram
3	Max GEQ Sum	CF 1691D	Medium (1800)	Stack to find dominance range + prefix sums
4	Imbalanced Array	CF 817D	Medium (1900)	Contribution technique for subarray min/max
5	Skyscrapers (Hard)	CF 1313C2	Medium (1900)	Histogram variant—maximize total under unimodal shape
6	Yet Another Yet Another Task	CF 1359D	Medium-Hard (2000)	Max subarray sum minus subarray max
7	Discrete Centrifugal Jumps	CF 1407D	Hard (2200)	Monotonic stack to build DP transition graph

---

When NOT to Use This

• Sliding window min/max (fixed window size): Need element expiry from both ends—use Monotonic Queue (deque), not stack
• Range min/max with arbitrary query endpoints: Use Sparse Table or Segment Tree
• k-th largest element: Monotonic stack gives nearest-neighbor relationships, not global ranking—use heap or quickselect
• Dynamic updates: Monotonic stack is a one-pass offline technique. For online queries with updates, use a Segment Tree

---

Debug This

Bug 1: Storing values instead of indices

stack<int> stk;
for (int i = 0; i < n; i++) {
    while (!stk.empty() && stk.top() < a[i]) {
        // BUG: stk.top() is a value, not an index
        // Can't set nge[???] -- we lost the index information!
        stk.pop();
    }
    stk.push(a[i]);  // BUG: pushing value, not index
}

Fix: Push and compare indices: stk.push(i) and a[stk.top()] < a[i].

Bug 2: Histogram width calculation

int ht = h[stk.back()]; stk.pop_back();
int w = i - stk.back();  // BUG: should be i - stk.back() - 1

Fix: Width is i - stk.back() - 1 (exclusive boundaries). If stack is empty after pop, width is i.

Bug 3: Missing cleanup for histogram

for (int i = 0; i < n; i++) {
    while (!stk.empty() && h[stk.back()] >= h[i]) {
        // compute area...
        stk.pop_back();
    }
    stk.push_back(i);
}
// BUG: elements remaining on stack are never processed!

Fix: Iterate i from 0 to n (inclusive). When i == n, use height 0 as a virtual sentinel that pops everything.

Bug 4: Wrong comparison for "next greater or equal"

// Goal: find next greater OR EQUAL element
while (!stk.empty() && a[stk.back()] < a[i]) {  // BUG: < means STRICTLY greater
    nge[stk.back()] = i;
    stk.pop_back();
}

Fix: Use <= to pop on equal values too: a[stk.back()] <= a[i].

Further Reading

• cp-algorithms—Minimum Stack / Minimum Queue—related pattern for maintaining min/max in a stack or queue
• Codeforces EDU—Monotonic Stack—step-by-step interactive course
• Monotonic queue (sliding window min/max): see 05-monotonic-queue.md
• For foundational stack operations and usage: see 01-stack-queue-deque.md
• Data structure selection guide: see ../11-contest-craft/06-data-structure-selection-guide.md
• Practice ladder for data structures: see ../12-practice-ladders/06-ladder-data-structures.md

---

Next Up: Monotonic Queue—extending the monotonic stack idea with element expiry for sliding window problems.