Monotonic Stack

How to think about it

Keep a stack of indices whose values are monotone (increasing or decreasing). When a new value breaks the order, pop and resolve those indices: the newcomer is their next greater/smaller. Each index is pushed and popped at most once.

Template shapes

Shape	Core move	Notes
Next greater right	Pop while top < current	Answer[top]=current
Next smaller	Flip the comparison	Same structure
Histogram	Previous + next smaller	Width = R-L-1

Complexity baseline

O(n) time (amortized one push/pop per index), O(n) stack space.

From template to problem

1. Decide direction (left-to-right or right-to-left) and monotone order.
2. Iterate; while stack top can be resolved by current, pop and write the answer.
3. Push current index.
4. Drain remaining stack with sentinel answers (-1 or n).

/** Monotonic stack template: next greater element to the right (−1 if none). */
export function nextGreater(nums: number[]): number[] {
  const n = nums.length;
  const ans = new Array<number>(n).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack.at(-1)!]! < nums[i]!) {
      ans[stack.pop()!] = nums[i]!;
    }
    stack.push(i);
  }
  return ans;
}

/** Monotonic stack template: next greater element to the right (−1 if none). */
export function nextGreater(nums: number[]): number[] {
  const n = nums.length;
  const ans = new Array<number>(n).fill(-1);
  const stack: number[] = [];
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack.at(-1)!]! < nums[i]!) {
      ans[stack.pop()!] = nums[i]!;
    }
    stack.push(i);
  }
  return ans;
}