pattern heroPT–23LeetCode Extension

Monotonic stack

Keep the items still waiting for an answer on a pile, from bigger to smaller. A new item takes off the top every item it beats and answers them at once, so no item is compared with everything after it.

P08 Monotonic stack1×

Example problem: for each day of [73, 74, 75, 71, 69, 72, 76], how many days until a warmer one.

073174275371469572676tempsanswer0000000stack—
not reachedcurrent daywaiting on the stacktop being checkedanswer found

Every answer starts at 0

answer = [0, 0, 0, 0, 0, 0, 0]stack = –day = –prev = –
01/42
restart · back · play · step
Speed
1function dailyTemperatures(temps):
2 answer = list of len(temps) zeros
3 stack = empty stack
4 for day from 0 to len(temps) - 1:
5 while day is warmer than the top:
6 prev = pop from stack
7 answer[prev] = day - prev
8 push day onto stack
9 return answer

← → step · space play/pause

How to recognise

for each element, the next or previous one that is greater or smaller: the next warmer day, the nearest taller bar.

How to solve problems like this

  1. Name what each element waits for: the next greater one or the next smaller one.
  2. Keep a stack of the indices still waiting. Indices, not values, so you can measure distances.
  3. For each new element, pop while it beats the top (greater, or smaller). Each popped index has found its answer.
  4. Push the new index. Indices left on the stack at the end have no answer: give them the default.

Where it's used

  • Convex hull. Graham's scan, which GEOS and PostGIS use for ST_ConvexHull, goes round the points and keeps the hull's border on a stack. A new point pops the points that turned out to be inside, the way a monotonic stack pops the items a new one beats.
  • Reading formulas. The shunting-yard algorithm keeps operators on a stack in order of priority. A new operator first pops every operator that binds at least as tightly. That is how calculators and formula parsers turn 2 + 3 × 4 into the order of work.