Monotonic Stack Problem

Problem Representative monotonic-stack task for this round: Next Greater Element — for each array element, find the first element to its right that is strictly greater (-1 if none). Master the pattern; the round uses a problem of this shape.

Input / Output

• Input: int array nums. Output: int array of next-greater values (or indices/distances per variant).

Constraints

• n up to 10^5 — the O(n^2) per-element scan is the baseline to beat; O(n) expected.

Example

• [2,1,2,4,3] → [4,2,4,-1,-1]; distances variant (Daily Temperatures): [73,74,75,71,69,72] → [1,1,3,2,1,-1... per its rules].

Expected approach

• Scan left to right with a stack of indices whose answer is unresolved, kept monotonically DECREASING by value: when nums[i] exceeds the top, pop and record nums[i] as the popped index's answer; push i. Each index pushed/popped once → O(n)/O(n). Know the family and which monotonic direction each needs: Daily Temperatures, Next Smaller Element, Stock Span, Largest Rectangle in Histogram (increasing stack + sentinel), Trapping Rain Water. Articulating WHY the stack stays monotone — popped elements can never be the answer for anyone later — is the interview substance.