Monotonic Stack

1. The signal

• “For every item, find the next greater/smaller item.”
• “How long until a larger value appears?”
• “How far can this height extend before something shorter?”
• “Merge with the nearest group ahead if you catch it.”

Brute force looks forward from every index. The waste is rescanning future values. A monotonic stack flips the direction: let each new value resolve all older values it can answer.

2. Pick the invariant from the question

For Daily Temperatures, the stack contains unresolved days with decreasing temperatures. A warmer current day pops every colder day it answers.

vector<int> answer(n, 0), st;
for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.back()] < a[i]) {
        int j = st.back(); st.pop_back();
        answer[j] = i - j;
    }
    st.push_back(i);
}

const answer = new Array(a.length).fill(0), stack = [];
for (let i = 0; i < a.length; i++) {
  while (stack.length && a[stack.at(-1)] < a[i]) {
    const j = stack.pop();
    answer[j] = i - j;
  }
  stack.push(i);
}

3. Why it is O(n)

Do not say “there is a nested loop, therefore O(n²).” Count how many times an index can cross the stack boundary:

• pushed once,
• popped at most once,
• never pushed again.

Across all iterations there are at most n pushes and n pops: O(2n) = O(n). This is the same amortised reasoning used by the sliding-window deque.

4. The histogram upgrade: carry the start

In Largest Rectangle in Histogram, a popped height is finished, but its left boundary is still useful. Carry that start into the new shorter height. The stack stores (start, height), not only an index.

A virtual height 0 after the array closes every bar still on the stack. This sentinel removes a second cleanup loop and is a reusable technique.

5. Car Fleet is monotonic after sorting

Sort cars from closest to the target to farthest and compute arrival time. If a car behind arrives no later than the fleet ahead, it catches that fleet. Only a strictly later arrival time creates a new fleet. The stack is monotonic in fleet arrival time.

6. Traps

1. Wrong comparison (< vs <=). Equal values sometimes resolve each other and sometimes do not; derive it from the exact wording.
2. Storing values when distance is required. Store indices for i - previousIndex.
3. Forgetting unresolved defaults. In next-greater problems they usually stay 0 or −1.
4. Pushing before popping. The current item should first resolve candidates, then become a candidate itself.
5. Memorising the histogram code. Remember the invariant: every entry owns the earliest start through which its height remains valid.

7. Learning order

1. Daily Temperatures — direct next-greater template.
2. Car Fleet — sort, transform to arrival time, then keep survivors.
3. Largest Rectangle — start propagation and a sentinel; the Week 3 mastery check.