Monotonic Stack — The Complete Guide

function nextGreater(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = []; // indices, values in decreasing order

  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()!] = nums[i]; // nums[i] is the next greater
    }
    stack.push(i);
  }

  return result;
}
// Stack invariant: values at stack indices are DECREASING
// When nums[i] > stack top → pop (found next greater for that element)

function nextSmaller(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = []; // indices, values in increasing order

  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack[stack.length - 1]] > nums[i]) {
      result[stack.pop()!] = nums[i]; // nums[i] is the next smaller
    }
    stack.push(i);
  }

  return result;
}
// Stack invariant: values at stack indices are INCREASING
// When nums[i] < stack top → pop (found next smaller for that element)

function prevGreater(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = []; // indices, values in decreasing order

  for (let i = 0; i < n; i++) {
    // Pop elements that are NOT greater than nums[i]
    while (stack.length && nums[stack[stack.length - 1]] <= nums[i]) {
      stack.pop();
    }
    // Stack top (if exists) is the previous greater element
    if (stack.length) {
      result[i] = nums[stack[stack.length - 1]];
    }
    stack.push(i);
  }

  return result;
}
// Key difference from "next greater": the ANSWER is read from the stack
// top, not assigned during the pop. The pop just cleans up irrelevant elements.

function prevSmaller(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = []; // indices, values in increasing order

  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack[stack.length - 1]] >= nums[i]) {
      stack.pop();
    }
    if (stack.length) {
      result[i] = nums[stack[stack.length - 1]];
    }
    stack.push(i);
  }

  return result;
}
// Stack invariant: values at stack indices are INCREASING
// Stack top after cleanup = nearest previous smaller element

function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  const stack: number[] = []; // increasing stack of indices
  let maxArea = 0;

  for (let i = 0; i <= n; i++) {
    // Use 0 as a sentinel to flush remaining bars
    const currHeight = i < n ? heights[i] : 0;

    while (stack.length && heights[stack[stack.length - 1]] > currHeight) {
      const height = heights[stack.pop()!];
      // Width: from previous smaller (stack top) to current (next smaller)
      const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      maxArea = Math.max(maxArea, height * width);
    }

    stack.push(i);
  }

  return maxArea;
}
// For each bar: area = height × (nextSmaller - prevSmaller - 1)
// The stack gives us both boundaries in one pass.
// Sentinel value 0 at the end forces all remaining bars to be processed.

function sumSubarrayMins(arr: number[]): number {
  const MOD = 1e9 + 7;
  const n = arr.length;
  const prevSmaller = new Array(n).fill(-1);  // index of prev smaller
  const nextSmaller = new Array(n).fill(n);   // index of next smaller

  const stack: number[] = [];

  // Previous smaller (strictly less)
  for (let i = 0; i < n; i++) {
    while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {
      stack.pop();
    }
    prevSmaller[i] = stack.length ? stack[stack.length - 1] : -1;
    stack.push(i);
  }

  stack.length = 0;

  // Next smaller (strictly less — use <= to handle duplicates)
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length && arr[stack[stack.length - 1]] > arr[i]) {
      stack.pop();
    }
    nextSmaller[i] = stack.length ? stack[stack.length - 1] : n;
    stack.push(i);
  }

  let sum = 0;
  for (let i = 0; i < n; i++) {
    const left = i - prevSmaller[i];   // subarrays extending left
    const right = nextSmaller[i] - i;  // subarrays extending right
    sum = (sum + arr[i] * left * right) % MOD;
  }

  return sum;
}
// Key: use strict < for one direction and <= for the other
// to avoid double-counting when there are duplicate values.

Input: [4, 2, 1, 5, 3]
Stack stores INDICES. We show values in parentheses for clarity.

i=0, nums[0]=4
  Stack empty → push 0
  Stack: [0(4)]

i=1, nums[1]=2
  2 < 4 → don't pop → push 1
  Stack: [0(4), 1(2)]

i=2, nums[2]=1
  1 < 2 → don't pop → push 2
  Stack: [0(4), 1(2), 2(1)]

i=3, nums[3]=5
  5 > 1 → pop 2 → result[2] = 5  (1's next greater is 5)
  5 > 2 → pop 1 → result[1] = 5  (2's next greater is 5)
  5 > 4 → pop 0 → result[0] = 5  (4's next greater is 5)
  Stack empty → push 3
  Stack: [3(5)]

i=4, nums[4]=3
  3 < 5 → don't pop → push 4
  Stack: [3(5), 4(3)]

Done. Remaining in stack → no next greater → -1.

Result: [5, 5, 5, -1, -1]

Key observation: When 5 arrived, it resolved THREE elements at once.
That's the power of the monotonic stack — batch resolution.

Heights: [2, 1, 5, 6, 2, 3]
Append sentinel 0: [2, 1, 5, 6, 2, 3, 0]
Stack stores indices. Increasing stack (by height).

i=0, h=2: Stack empty → push 0.  Stack: [0]
i=1, h=1: 1 < 2 → pop 0.
           height=2, width=1 (no stack left, so width=i=1)
           area = 2×1 = 2. maxArea=2
           push 1.  Stack: [1]

i=2, h=5: 5 > 1 → push 2.  Stack: [1, 2]
i=3, h=6: 6 > 5 → push 3.  Stack: [1, 2, 3]

i=4, h=2: 2 < 6 → pop 3.
           height=6, width = 4-2-1 = 1. area=6. maxArea=6
           2 < 5 → pop 2.
           height=5, width = 4-1-1 = 2. area=10. maxArea=10 ★
           2 ≥ 1 → stop. push 4.  Stack: [1, 4]

i=5, h=3: 3 > 2 → push 5.  Stack: [1, 4, 5]

i=6, h=0 (sentinel): flushes everything.
           pop 5: height=3, width=6-4-1=1. area=3.
           pop 4: height=2, width=6-1-1=4. area=8.
           pop 1: height=1, width=6 (stack empty). area=6.

Final maxArea = 10 (bar of height 5, spanning indices 2-3)

The sentinel (height 0) guarantees all bars get processed.
Width formula: stack empty → width = i. Otherwise → i - stack.top - 1.

Temps: [73, 74, 75, 71, 69, 72, 76, 73]
Stack stores indices. Decreasing stack (by temperature).

i=0, t=73: push 0.  Stack: [0(73)]
i=1, t=74: 74>73 → pop 0 → result[0]=1-0=1. push 1.  Stack: [1(74)]
i=2, t=75: 75>74 → pop 1 → result[1]=2-1=1. push 2.  Stack: [2(75)]
i=3, t=71: 71<75 → push 3.  Stack: [2(75), 3(71)]
i=4, t=69: 69<71 → push 4.  Stack: [2(75), 3(71), 4(69)]
i=5, t=72: 72>69 → pop 4 → result[4]=5-4=1.
           72>71 → pop 3 → result[3]=5-3=2.
           72<75 → stop. push 5.  Stack: [2(75), 5(72)]
i=6, t=76: 76>72 → pop 5 → result[5]=6-5=1.
           76>75 → pop 2 → result[2]=6-2=4.
           push 6.  Stack: [6(76)]
i=7, t=73: 73<76 → push 7.  Stack: [6(76), 7(73)]

Remaining → result stays 0 (no warmer day).

Result: [1, 1, 4, 2, 1, 1, 0, 0]

Notice: result[i] = j - i (distance), not the temperature itself.
This is a "next greater" problem where the answer is the INDEX DISTANCE.

What does the problem ask?
├── "Next greater element" for each position?
│   → Decreasing stack, scan left→right, answer on POP
├── "Next smaller element" for each position?
│   → Increasing stack, scan left→right, answer on POP
├── "Previous greater element" for each position?
│   → Decreasing stack, scan left→right, answer = STACK TOP
├── "Previous smaller element" for each position?
│   → Increasing stack, scan left→right, answer = STACK TOP
├── "Largest rectangle in histogram"?
│   → Increasing stack + sentinel. Area = height × width on pop
├── "Sum of subarray mins/maxs"?
│   → Find prev & next smaller/greater. Contribution = val × left × right
├── "Stock span" or "days until warmer"?
│   → Previous/next greater. Answer = index distance
├── Circular array?
│   → Same template but iterate 2n times with i % n
└── Not sure?
    → Ask: "Can I rephrase this as 'nearest greater/smaller'?"
    ├── YES → Pick the right template above
    └── NO  → Probably not a monotonic stack problem