Stacks and monotonic deques

A stack holds unfinished work where the newest item is handled first: brackets waiting to close, an expression being evaluated, recursive calls, or items waiting for a later event. In valid parentheses, each closing bracket must match the most recent bracket still open. Counting brackets can't tell whether the types nest correctly.

In Daily Temperatures, keep the indexes of days still waiting for a warmer day. Their temperatures never rise from the bottom of the stack to the top. When a strictly warmer day arrives, it answers the days at the top. It's their first warmer day, because every day in between failed to answer them. Each index is pushed once and popped once, so it's O(n) time and O(n) space.

Equal values matter. For "next strictly greater", an equal value doesn't answer a waiting index. For "next greater or equal", it does. The comparison in a monotonic stack is exactly the problem's rule.

A monotonic deque adds a way for items to expire from the front. For the maximum of each fixed-size window, keep indexes in time order, with values decreasing from front to back. Remove expired indexes from the front. Before adding a new value, remove smaller or equal values from the back. The new value is at least as big and stays longer, so they can never win again. The front is the current maximum. You could keep equal values instead, as long as you handle expiry correctly.

Shortest Subarray with Sum at Least K combines prefix sums and a monotonic deque. For prefix positions j < i, the range sum is P[i] − P[j]. Keep the prefix sums in the deque in increasing order. If a later prefix sum is no larger than an earlier one, the later start gives at least as big a sum and a shorter range, so drop the earlier one. At the front, whenever a range reaches k, record it and drop that start: any later end would only make it longer.

That explains both ends of the deque. It also explains why the positive-numbers sliding window from Chapter 8 doesn't work with negative numbers.

Practice: LC 20 Valid Parentheses, LC 155 Min Stack, LC 739 Daily Temperatures, LC 496 Next Greater Element I, LC 239 Sliding Window Maximum, LC 862 Shortest Subarray with Sum at Least K, LC 84 Largest Rectangle in Histogram.

Check your understanding: Was an item removed because it expired, got answered, or could never win? Give a different reason for each kind of removal. For the histogram problem, say exactly which bar stops each height from extending further.