Scan i. While a[i] satisfies resolve(a[stack[-1]],a[i]), pop j and finalize its right boundary as i. Push i afterward, preserving the chosen value monotonicity.
Recognition signals
Each position needs its first or nearest greater/smaller neighbor.
A candidate becomes permanently determined when a dominating item arrives.
Each value's interval of influence as a minimum or maximum is needed.
Naive bidirectional scans cost O(n²), but unresolved candidates can be compressed in order.
False friends
Signal
Why it is different
Arbitrary range-maximum queries
A monotonic stack finds nearest boundaries, not general online interval extrema.
Sliding-window extrema
Candidates also expire by position, requiring a two-ended monotonic deque.
Core invariant
Stack indexes increase, their values are monotone in the chosen direction, and every stored index has not yet encountered a right-side item that resolves it.
State, transition, and processing order
Item
Definition
State
Index stack, current index/value, strictness choice (> versus ≥), and result array.
Transition
Repeatedly pop candidates resolved by the new value and write their answers; when no more resolve, push the current index.
Frontier / order
All nondominated candidates still lacking a right answer; a popped candidate can never matter again.
Python skeleton
def next_strictly_greater(values):
answer = [-1] * len(values)
stack = [] # indexes, values strictly decreasing
for i, value in enumerate(values):
while stack and values[stack[-1]] < value:
j = stack.pop()
answer[j] = i
stack.append(i)
return answer
Correctness sketch
When j pops, the current value is greater, and every earlier scanned value while j remained on stack failed to pop it, so i is its first strictly greater position.
Unpopped candidates remain value-monotone and every candidate dominated by the new value has been resolved.
Each index enters once and exits at most once; any index left at end truly has no greater value to its right.
Complexity
Time
Space
Parameters
O(n)
O(n)
Despite the nested while, each index is pushed and popped at most once over the complete scan.
Edge cases
Empty input returns an empty result.
Strict versus non-strict comparison changes ownership of duplicate values.
A decreasing input can grow the stack to n.
For left boundaries, scan in reverse or inspect the top before pushing.
Error patterns
Pattern
Why it fails / fix
Storing values when indexes are needed
Distances, boundaries, and duplicate handling usually require indexes.
Swapping < and <= casually
Duplicates may be double-counted or omitted; strictness must follow the definition.
Calling the nested loop O(n²)
Use the at-most-one-pop-per-index amortized argument.
Selection and exclusion rules
First or nearest greater/smaller strongly suggests a monotonic stack.
If candidates also expire from a window, use a monotonic deque.
For contribution counting, first find left and right dominance boundaries, then combine spans.