LeetCode Patterns Flashcards: Stack, Monotonic Stack, Valid Parentheses, Next Greater

The stack pattern uses a last-in-first-out data structure to process elements in reverse order, match pairs, or track state that needs to be unwound. Use it when the problem involves matching opening and closing symbols like parentheses, processing elements in reverse of their arrival order, evaluating expressions, maintaining a history that can be undone, or finding the next greater or smaller element. The stack naturally handles nested structures because the most recently opened scope is the first one closed. Most stack problems run in O of n time and O of n space.

Iterate through the string character by character. When you encounter an opening bracket, push it onto the stack. When you encounter a closing bracket, check if the stack is empty, which means no matching opener, or if the top of the stack does not match the closing type. If either condition is true, the string is invalid. If it matches, pop the stack. After processing all characters, the string is valid only if the stack is empty, meaning every opener was matched. This runs in O of n time. The stack naturally handles nested brackets like parentheses inside square brackets inside curly braces.

A monotonic stack is a stack where elements are kept in strictly increasing or decreasing order. When a new element violates the monotonic property, elements are popped until the property is restored. During each pop, you discover a relationship between the popped element, the new element, and the remaining stack top. Monotonic stacks solve "next greater element," "next smaller element," "largest rectangle in histogram," and "daily temperatures" in O of n time. Each element is pushed and popped at most once.

Iterate through the array from right to left, maintaining a stack of elements in decreasing order from bottom to top. For each element, pop all elements from the stack that are smaller than or equal to the current element because they cannot be the next greater element for anyone to the left. The stack top after popping, if it exists, is the next greater element. Then push the current element. If the stack is empty after popping, there is no greater element to the right. Each element enters and leaves the stack at most once, giving O of n total time despite the nested loop appearance.

Maintain a stack of indices where corresponding temperatures form a decreasing sequence. For each new day, while the stack is not empty and the current temperature is higher than the temperature at the stack top index, pop the index and record the difference between the current index and the popped index as the number of days to wait. Then push the current index. Elements remaining on the stack after processing have no warmer future day, so their answer is zero. This runs in O of n time because each index is pushed and popped exactly once.

Maintain an increasing monotonic stack of bar indices. When a bar shorter than the stack top is encountered, the taller bars can no longer extend right, so pop them and calculate their rectangle area. The width extends from the current index back to the new stack top plus one. Track the maximum area found. After processing all bars, pop remaining bars using the array length as the right boundary. This runs in O of n time. The key insight is that each bar's maximum rectangle is bounded by the first shorter bar on its left and right, and the monotonic stack efficiently finds both boundaries.

Reverse Polish notation, also called postfix notation, places operators after their operands. Process tokens left to right: when a number is encountered, push it onto the stack. When an operator is encountered, pop two operands from the stack, apply the operation with the second popped value as the left operand and the first popped as the right, then push the result. After all tokens are processed, the stack contains exactly one element, which is the final answer. ---