Skip to content

Monotonic Stack / Queue Hot Sheet

Use this sheet when one linear scan plus one permanent domination rule is enough.

Do Not Use When

  • updates happen online after the scan starts
  • the active set is not monotone and old candidates may become relevant again
  • the query is an arbitrary interval rather than one structured scan -> Sparse Table hot sheet, Segment Tree hot sheet
  • you need median / arbitrary quantile maintenance, not only min / max / nearest boundary

Choose By Signal

  • first smaller / greater to the left or right -> monotonic stack
  • largest rectangle / nearest blocking boundary -> monotonic stack with widths from indices
  • minimum / maximum of every fixed-width window -> monotonic deque
  • one DP transition asks for the best value over a forward-only interval -> monotonic deque
  • online interval queries or non-monotone activation -> ordered set / heap / segment tree instead

Core Invariants

  • the structure stores indices, not only values
  • the value order inside the stack / deque is monotone by the chosen comparator
  • once a new element dominates an older tail candidate, the older one can never matter again
  • every index is pushed once and popped once, so the total pop count is O(n)

Main Traps

  • mixing < and <= tie policy; equal values change whether you want strictly smaller or smaller-or-equal
  • storing only values and then losing the boundary / width / expiry information
  • forgetting that deque expirations happen from the front, while domination pops happen from the back
  • reaching for segment tree or multiset before checking whether one monotone sweep already closes the whole statement

Exact Starter Route

Reopen Paths