Stacks & Monotonic Stack

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A stack touches only its top: push, pop, peek — all O(1). Last in, first out: the most recent unfinished thing is handled first.

   #1
2. ↯use it when

   Brackets and tags that nest, undo, postfix, k[...], .. in paths, things that collide or cancel — wherever the newest item settles first.

   #2
3. ↯use it when

   "Next greater / smaller", "days until warmer", the widest rectangle → a monotonic stack of indices.

   #3
4. { }template

   while (!st.isEmpty() && a[st.peek()] < a[i]) ans[st.pop()] = a[i]; st.push(i); — each pop gets its answer from the newcomer.

   #4
5. O( )cost

   Each index is pushed once and popped at most once → O(n) time, even with a while inside the for. Stack space: O(n) worst case.

   #5
6. !trap

   pop() on an empty ArrayDeque throws; peek() returns null. Check isEmpty() first — and check the stack is empty at the end.

   #6
7. !trap

   stack.peek() == mins.peek() on two Integers compares references: fine up to 127, wrong for 1000. Unbox to int first.

   #7
8. !trap

   Postfix: the first pop() is the right operand. For a b -, pop b, then a, push a − b.

   #8
9. ✦pro tip

   Use Deque<Integer> st = new ArrayDeque<>(), not legacy Stack. Push indices, not values, so you can measure distances and widths.

   #9

Shaky on a card? Open the chapter or flip its recall cards.