Micro-Drill #249 — When to use monotonic stack

WHEN TO USE MONOTONIC STACK
───────────────────────────
SIGNAL PHRASES:
  "next greater/smaller element"
  "previous greater/smaller element"
  "span" / "days until warmer"
  "largest rectangle in histogram"
  "stock span problem"

PATTERN:
  stack = []  # stores indices, monotonic order
  for i in range(n):
      while stack and a[stack[-1]] < a[i]:  # or >
          j = stack.pop()
          # a[j]'s next greater is a[i]
          # a[j]'s previous greater is stack[-1] (if exists)
      stack.append(i)

MONOTONIC INCREASING STACK: finds next smaller
MONOTONIC DECREASING STACK: finds next greater

WHEN NOT monotonic stack:
  × Sliding window max → use deque (not just stack)
  × Need both prev AND next → two passes or one pass
  × No "nearest" relationship → wrong tool

COMPLEXITY: O(n) — each element pushed and popped once