Base Monotonic Stack

Base Mono Stack

When To Use

Use this when each index needs the nearest greater/smaller element on one side.

This is the prerequisite for most monotonic stack patterns.

Template

for i in scan order:
    while stack not empty and stack.top is worse than current:
        pop
 
    answer may use stack.top
    push i

Scan left-to-right for previous elements.

Scan right-to-left for next elements.

Two Basic Implementations

Candidate List

Use this when the current index wants to query the nearest surviving candidate before pushing itself.

for i in scan order:
    while stack not empty and should_pop(nums[stack.top], nums[i]):
        pop
 
    if stack not empty:
        ans[i] = stack.top
 
    push i

Example: previous greater element.

should_pop(top, cur) = top <= cur

Waiting Room

Use this when earlier indices are waiting for the current index to resolve them.

for i in scan order:
    while stack not empty and current resolves stack.top:
        ans[stack.top] = i
        pop
 
    push i

Example: next greater element to the right.

current resolves top = nums[i] > nums[top]

Problems

Next Greater Element II

Problem: find the next greater value in a circular array.

Pattern: scan twice from the right.

Applied pseudocode:

for idx = 2 * n - 1 down to 0:
    i = idx % n
 
    while stack not empty and nums[stack.top] <= nums[i]:
        pop
 
    if idx < n and stack not empty:
        ans[i] = nums[stack.top]
 
    push i

Online Stock Span

Problem: for each price, count consecutive previous prices <= current.

Pattern: previous greater boundary.

Number of Visible People in a Queue

Problem: count how many people each person can see to the right.

Pattern: count popped shorter people, plus one blocking taller person.

132 Pattern

Problem: detect indices i < j < k with nums[i] < nums[k] < nums[j].

Pattern: stack stores structured candidates, not just a single boundary.