🎯 Stack Patterns
1️⃣ Core Framework
When discussing Stack Patterns, I frame it as:
- What problem pattern stack solves
- LIFO behavior
- Valid parentheses
- Monotonic stack
- Next greater element
- Daily temperatures
- Largest rectangle in histogram
- Stack for expression evaluation
- Stack for DFS / backtracking simulation
- Senior-level explanation
2️⃣ What Problem Are We Solving?
A stack is useful when the most recent unresolved item should be processed first.
It is commonly used for:
- Parentheses matching
- Expression evaluation
- Undo operations
- Function call simulation
- DFS traversal
- Monotonic stack problems
- Next greater / next smaller element
- Histogram area
- Removing adjacent elements
- Parsing nested structures
The core idea is:
Last In, First Out
The last item pushed into the stack is the first item popped out.
👉 Interview Answer
A stack is a data structure that follows Last In, First Out behavior.
It is useful when the most recent unresolved state should be handled first.
In interviews, stack patterns commonly appear in parentheses matching, expression parsing, DFS simulation, and monotonic stack problems like next greater element or largest rectangle in histogram.
3️⃣ Why Stack Works
LIFO Behavior
Stack operations:
push → add item to top
pop → remove item from top
peek → inspect top item
Example:
push 1
push 2
push 3
pop → 3
pop → 2
pop → 1
Why This Matters
Many problems naturally depend on the latest unresolved item.
For example:
Opening bracket must match the nearest closing bracket.
So:
"("
"["
"{"
The most recent opening bracket must be matched first.
👉 Interview Answer
Stack works when the problem has a nested or last-unresolved-first structure.
For parentheses, the most recent opening bracket must be closed first.
For monotonic stack, the top of the stack represents the most recent candidate that has not yet found its next greater or smaller value.
4️⃣ Valid Parentheses
Problem
Given a string containing brackets, determine whether it is valid.
"()" → true
"()[]{}" → true
"(]" → false
"([)]" → false
"{[]}" → true
Code
def is_valid(s):
stack = []
pairs = {
")": "(",
"]": "[",
"}": "{"
}
for char in s:
if char in pairs.values():
stack.append(char)
elif char in pairs:
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return len(stack) == 0
Key Insight
When we see a closing bracket:
It must match the most recent opening bracket.
That is exactly stack behavior.
👉 Interview Answer
Valid parentheses is a classic stack problem.
I push opening brackets into the stack.
When I see a closing bracket, I check whether it matches the top of the stack.
If it does not match, the string is invalid.
At the end, the stack must be empty.
5️⃣ Min Stack
Problem
Design a stack that supports:
push
pop
top
getMin
All in:
O(1)
Code
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack:
self.min_stack.append(val)
else:
self.min_stack.append(min(val, self.min_stack[-1]))
def pop(self):
self.stack.pop()
self.min_stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
Key Insight
Keep another stack where each position stores:
minimum value up to this point
👉 Interview Answer
For Min Stack, I use two stacks.
The normal stack stores values.
The min stack stores the minimum value at each depth.
This way, getMin can return the top of the min stack in O(1).
6️⃣ Remove Adjacent Duplicates
Problem
Remove adjacent duplicate characters.
"abbaca" → "ca"
Explanation:
abbaca
remove bb → aaca
remove aa → ca
Code
def remove_duplicates(s):
stack = []
for char in s:
if stack and stack[-1] == char:
stack.pop()
else:
stack.append(char)
return "".join(stack)
Key Insight
The latest character may cancel with the current character.
So we compare against:
stack[-1]
👉 Interview Answer
I use a stack because each new character only needs to compare with the most recent unresolved character.
If the top of the stack equals the current character, they cancel out.
Otherwise, I push the current character.
The remaining stack forms the final string.
7️⃣ Stack for Expression Evaluation
Problem Pattern
Stacks are useful for evaluating expressions such as:
Reverse Polish Notation
Basic Calculator
Decode String
Nested expressions
Reverse Polish Notation Example
["2", "1", "+", "3", "*"]
This means:
(2 + 1) * 3 = 9
Code
def eval_rpn(tokens):
stack = []
for token in tokens:
if token not in {"+", "-", "*", "/"}:
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == "+":
stack.append(a + b)
elif token == "-":
stack.append(a - b)
elif token == "*":
stack.append(a * b)
else:
stack.append(int(a / b))
return stack[-1]
👉 Interview Answer
For Reverse Polish Notation, operands are pushed onto the stack.
When we see an operator, we pop the last two operands, apply the operator, and push the result back.
Stack works because the expression naturally uses the most recent operands first.
8️⃣ Decode String
Problem
Decode encoded strings like:
"3[a]2[bc]" → "aaabcbc"
"3[a2[c]]" → "accaccacc"
Code
def decode_string(s):
stack = []
current = ""
number = 0
for char in s:
if char.isdigit():
number = number * 10 + int(char)
elif char == "[":
stack.append((current, number))
current = ""
number = 0
elif char == "]":
previous, count = stack.pop()
current = previous + current * count
else:
current += char
return current
Key Insight
Nested structures require remembering previous context.
Stack stores:
previous string
repeat count
👉 Interview Answer
Decode String is a stack problem because the input can be nested.
When I see an opening bracket, I save the current string and repeat count.
When I see a closing bracket, I pop the previous context and combine it with the decoded inner string.
Stack helps restore the most recent unfinished context.
9️⃣ Monotonic Stack
What Is a Monotonic Stack?
A monotonic stack keeps elements in increasing or decreasing order.
It is used to find:
- Next greater element
- Next smaller element
- Previous greater element
- Previous smaller element
- Span problems
- Histogram rectangle
- Temperature waiting days
Increasing Stack
bottom → top
small → large
Used when we want to find a smaller boundary or maintain increasing order.
Decreasing Stack
bottom → top
large → small
Used when we want to find a greater boundary or maintain decreasing order.
👉 Interview Answer
A monotonic stack is a stack that maintains elements in sorted order, either increasing or decreasing.
When the current element breaks the monotonic order, we pop elements and resolve their answer.
It is commonly used for next greater, next smaller, and histogram problems.
🔟 Next Greater Element
Problem
For each element, find the next greater element on its right.
nums = [2, 1, 2, 4, 3]
answer = [4, 2, 4, -1, -1]
Code
def next_greater_element(nums):
result = [-1] * len(nums)
stack = []
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
index = stack.pop()
result[index] = num
stack.append(i)
return result
What Stack Stores
The stack stores indexes whose next greater element has not been found yet.
unresolved indexes
👉 Interview Answer
For next greater element, I keep a decreasing stack of unresolved indexes.
When the current number is greater than the number at the top index, it becomes the next greater element for that index.
I keep popping until the stack order is restored, then push the current index.
1️⃣1️⃣ Daily Temperatures
Problem
For each day, return how many days to wait until a warmer temperature.
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
answer = [1, 1, 4, 2, 1, 1, 0, 0]
Code
def daily_temperatures(temperatures):
result = [0] * len(temperatures)
stack = []
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
prev_index = stack.pop()
result[prev_index] = i - prev_index
stack.append(i)
return result
Pattern
This is next greater element by index distance.
answer[prev_index] = current_index - prev_index
👉 Interview Answer
Daily Temperatures is a next greater element problem.
I keep a decreasing stack of indexes whose warmer day has not been found.
When the current temperature is warmer than the top index temperature, I pop that index and compute the distance.
1️⃣2️⃣ Online Stock Span
Problem
For each stock price, return how many consecutive days including today had price less than or equal to today’s price.
prices = [100, 80, 60, 70, 60, 75, 85]
span = [1, 1, 1, 2, 1, 4, 6]
Code
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price):
span = 1
while self.stack and self.stack[-1][0] <= price:
_, previous_span = self.stack.pop()
span += previous_span
self.stack.append((price, span))
return span
Key Insight
Store compressed information:
(price, span)
Instead of storing every previous day individually.
👉 Interview Answer
Stock span is a monotonic decreasing stack problem.
For each new price, I pop previous prices that are less than or equal to it.
Their spans can be merged into the current span.
This gives amortized O(1) time per operation.
1️⃣3️⃣ Largest Rectangle in Histogram
Problem
Given bar heights, find the largest rectangle area.
heights = [2, 1, 5, 6, 2, 3]
answer = 10
The largest rectangle is:
height 5 and 6
width 2
area 10
Key Insight
For each bar, find the first smaller bar on the left and right.
Then:
width = right_smaller_index - left_smaller_index - 1
area = height * width
Code
def largest_rectangle_area(heights):
stack = []
max_area = 0
extended = heights + [0]
for i, height in enumerate(extended):
while stack and extended[stack[-1]] > height:
h = extended[stack.pop()]
left_boundary = stack[-1] if stack else -1
width = i - left_boundary - 1
max_area = max(max_area, h * width)
stack.append(i)
return max_area
Why Add Sentinel Zero?
The final zero forces all remaining bars to be popped and processed.
👉 Interview Answer
Largest Rectangle in Histogram uses a monotonic increasing stack.
The stack stores indexes of bars in increasing height order.
When the current height is smaller than the stack top, we know the right boundary for the popped bar.
The new stack top becomes the left boundary.
This allows us to compute the largest rectangle where the popped bar is the limiting height.
1️⃣4️⃣ Maximal Rectangle
Problem
Given a binary matrix, find the largest rectangle containing only 1s.
Key Idea
Convert each row into a histogram.
For each row:
height[c] = number of consecutive 1s above current row
Then apply:
largest rectangle in histogram
Code
def maximal_rectangle(matrix):
if not matrix or not matrix[0]:
return 0
rows = len(matrix)
cols = len(matrix[0])
heights = [0] * cols
best = 0
for r in range(rows):
for c in range(cols):
if matrix[r][c] == "1":
heights[c] += 1
else:
heights[c] = 0
best = max(best, largest_rectangle_area(heights))
return best
👉 Interview Answer
Maximal Rectangle can be reduced to Largest Rectangle in Histogram.
For each row, I treat it as the bottom of a histogram.
Each column height represents consecutive ones ending at that row.
Then I run the histogram stack algorithm for each row.
1️⃣5️⃣ Asteroid Collision
Problem
Each asteroid moves left or right.
Positive means moving right.
Negative means moving left.
When two asteroids collide, the smaller one explodes.
Example
[5, 10, -5] → [5, 10]
[8, -8] → []
[10, 2, -5] → [10]
Code
def asteroid_collision(asteroids):
stack = []
for asteroid in asteroids:
alive = True
while alive and asteroid < 0 and stack and stack[-1] > 0:
if stack[-1] < -asteroid:
stack.pop()
elif stack[-1] == -asteroid:
stack.pop()
alive = False
else:
alive = False
if alive:
stack.append(asteroid)
return stack
Key Insight
Only this case collides:
previous asteroid moving right
current asteroid moving left
That is:
stack[-1] > 0 and asteroid < 0
👉 Interview Answer
Asteroid Collision uses a stack to keep unresolved asteroids.
A collision only happens when the previous asteroid moves right and the current asteroid moves left.
I keep resolving collisions against the stack top until the current asteroid is destroyed or there is no collision.
The remaining stack is the final state.
1️⃣6️⃣ Simplify Path
Problem
Simplify a Unix-style file path.
"/home/" → "/home"
"/../" → "/"
"/a/./b/../../c/" → "/c"
Code
def simplify_path(path):
stack = []
for part in path.split("/"):
if part == "" or part == ".":
continue
elif part == "..":
if stack:
stack.pop()
else:
stack.append(part)
return "/" + "/".join(stack)
Key Insight
Directory navigation has stack behavior:
folder → push
.. → pop
. → ignore
👉 Interview Answer
Simplify Path is a stack problem because directory traversal has nested state.
A normal folder name is pushed onto the stack.
A double dot means go back to the parent directory, so we pop if possible.
A single dot or empty part is ignored.
1️⃣7️⃣ Stack for DFS
Recursive DFS
Recursion uses the call stack implicitly.
def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
Iterative DFS
We can simulate recursion with an explicit stack.
def dfs_iterative(root):
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
Key Insight
Stack stores:
nodes we need to process later
👉 Interview Answer
DFS naturally uses stack behavior.
Recursive DFS relies on the call stack.
Iterative DFS uses an explicit stack to store nodes that still need to be processed.
This is useful when we want to avoid recursion depth issues or control traversal order manually.
1️⃣8️⃣ Stack vs Queue
Stack
Last In, First Out
Used for:
- DFS
- Backtracking
- Matching parentheses
- Monotonic stack
- Undo
- Nested parsing
Queue
First In, First Out
Used for:
- BFS
- Level-order traversal
- Shortest path in unweighted graph
- Task scheduling
Comparison
| Data Structure | Order | Common Use |
|---|---|---|
| Stack | LIFO | DFS, parsing, monotonic problems |
| Queue | FIFO | BFS, level-order traversal |
| Deque | Both ends | Sliding window max/min, BFS variants |
👉 Interview Answer
Stack is LIFO, so it is good for DFS, nested parsing, and resolving the most recent unresolved item.
Queue is FIFO, so it is good for BFS and level-order processing.
The choice depends on whether the problem needs last-in-first-out or first-in-first-out behavior.
1️⃣9️⃣ When Stack Applies
Good Fit
Use stack when the problem has:
Nested structure
Most recent unresolved item
Need to reverse processing order
Need to simulate recursion
Need next greater or next smaller element
Need matching pairs
Need rollback or undo behavior
Signals in Problems
Look for words like:
valid parentheses
next greater
previous smaller
histogram
nested
decode
simplify path
calculator
remove adjacent
DFS
👉 Interview Answer
I consider stack when the problem requires processing the most recent unresolved item first.
Typical signals include nested structures, matching pairs, expression evaluation, DFS traversal, and next greater or next smaller element problems.
If the problem asks for nearest greater or smaller values, I often think of monotonic stack.
2️⃣0️⃣ Common Edge Cases
Empty Input
s = ""
nums = []
root = None
Empty Stack Before Pop
Always check:
if stack:
stack.pop()
Remaining Items in Stack
At the end, decide whether remaining items mean:
valid unresolved state
or
invalid input
For parentheses:
remaining stack means invalid
For next greater element:
remaining stack means answer is -1
Duplicates
Important for monotonic stack:
use < or <=?
use > or >=?
This changes whether equal values are popped.
👉 Interview Answer
Common stack edge cases include empty input, popping from an empty stack, leftover stack items, and duplicate values in monotonic stack problems.
For monotonic stack, I pay close attention to whether the comparison should be strict or non-strict.
2️⃣1️⃣ Complexity Analysis
Basic Stack Problems
Usually:
Time: O(n)
Space: O(n)
Why O(n)?
Each element is usually:
pushed once
popped once
So even with a while loop, monotonic stack is often O(n) amortized.
Example
In next greater element:
Each index enters the stack once.
Each index leaves the stack once.
Total work is linear.
👉 Interview Answer
Most stack solutions are O(n) time and O(n) space.
For monotonic stack, even though there is a nested while loop, the total time is still O(n) amortized because each element is pushed once and popped once.
This amortized analysis is important to explain clearly in interviews.
2️⃣2️⃣ Common Mistakes
Mistake 1: Popping Without Checking Empty Stack
top = stack.pop()
without:
if stack:
Mistake 2: Wrong Monotonic Direction
For next greater element, we often maintain:
decreasing stack
For next smaller element, we often maintain:
increasing stack
Mistake 3: Storing Values Instead of Indexes
Sometimes we need distance or position.
For example:
Daily Temperatures needs index distance.
So store indexes, not just values.
Mistake 4: Mishandling Equal Values
Comparison choice matters:
<
<=
>
>=
Mistake 5: Not Explaining Amortized O(n)
Nested while loops may look like O(n²), but each element pops once.
👉 Interview Answer
Common mistakes include popping without checking stack emptiness, using the wrong monotonic direction, storing values when indexes are needed, mishandling equal values, and failing to explain amortized O(n).
I always define what the stack stores and what invariant it maintains.
2️⃣3️⃣ Standard Templates
Basic Stack Template
stack = []
for item in items:
if should_push(item):
stack.append(item)
else:
if not stack:
return invalid
top = stack.pop()
process(top, item)
Parentheses Template
def is_valid(s):
stack = []
pairs = {")": "(", "]": "[", "}": "{"}
for char in s:
if char in pairs.values():
stack.append(char)
elif char in pairs:
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return not stack
Monotonic Stack Template
stack = []
result = [-1] * len(nums)
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
index = stack.pop()
result[index] = num
stack.append(i)
Histogram Template
def largest_rectangle_area(heights):
stack = []
max_area = 0
for i, height in enumerate(heights + [0]):
while stack and heights_with_sentinel[stack[-1]] > height:
h = heights_with_sentinel[stack.pop()]
left = stack[-1] if stack else -1
width = i - left - 1
max_area = max(max_area, h * width)
stack.append(i)
return max_area
Iterative DFS Template
def dfs_iterative(root):
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
🧠 Staff-Level Answer Final
👉 Interview Answer Full Version
A stack is a Last In, First Out data structure.
It is useful when the most recent unresolved item should be processed first.
This pattern appears in parentheses matching, expression evaluation, nested parsing, DFS traversal, undo behavior, and monotonic stack problems.
For valid parentheses, the stack stores unmatched opening brackets. When a closing bracket appears, it must match the most recent opening bracket at the top of the stack. If it does not match, the input is invalid.
For expression evaluation, the stack stores operands or previous parsing context. In Reverse Polish Notation, when we see an operator, we pop the two most recent operands, apply the operation, and push the result back.
For nested parsing problems like Decode String, the stack stores previous context. When we enter a bracket, we save the current string and repeat count. When we close the bracket, we restore the previous context and combine it with the decoded inner string.
A major interview pattern is monotonic stack. A monotonic stack maintains elements in increasing or decreasing order. It is used for next greater element, daily temperatures, stock span, and largest rectangle in histogram.
The key idea is that when the current element breaks the monotonic order, we pop unresolved elements from the stack and resolve their answer.
For next greater element, the stack usually stores indexes in decreasing value order. When the current value is greater than the value at the top index, the current value is the next greater element for that index.
For largest rectangle in histogram, I use a monotonic increasing stack. When the current height is smaller than the stack top, the popped bar has found its right boundary. The new stack top gives the left boundary. That lets us compute the maximum rectangle where the popped bar is the limiting height.
Stack is also closely related to DFS. Recursive DFS uses the call stack implicitly, while iterative DFS uses an explicit stack.
At a senior level, I would always explain what the stack stores, what invariant the stack maintains, when elements are pushed, when elements are popped, and what it means when an element is popped.
Most stack algorithms are O(n) time and O(n) space. For monotonic stack, even if there is a while loop inside the for loop, the total work is O(n) amortized because each element is pushed once and popped once.
The main pitfalls are empty stack errors, storing values when indexes are needed, using the wrong monotonic direction, mishandling equal values, and not explaining the stack invariant clearly.
⭐ Final Insight
Stack Patterns 的核心不是“用 list append/pop”。
它的核心是处理 most recent unresolved state。
Senior-level 的重点是：
stack 里存什么， stack 维护什么 invariant， 什么时候 push， 什么时候 pop， pop 出来的元素代表什么问题被解决了。
对 monotonic stack 来说， 还要讲清楚为什么 nested while loop 仍然是 amortized O(n)。
能讲清楚这些， Stack 就不是一个简单数据结构， 而是一类处理 nested state、unresolved candidates 和 nearest boundary 的通用模式。
中文部分
🎯 Stack Patterns
1️⃣ 核心框架
讨论 Stack Patterns 时，我通常从：
- Stack 解决什么问题
- LIFO 行为
- Valid parentheses
- Monotonic stack
- Next greater element
- Daily temperatures
- Largest rectangle in histogram
- Expression evaluation
- DFS / backtracking simulation
- 高级工程师解释方式
2️⃣ 要解决什么问题？
Stack 适合处理：
最近出现、但还没有解决的问题。
它常用于：
- Parentheses matching
- Expression evaluation
- Undo operations
- Function call simulation
- DFS traversal
- Monotonic stack problems
- Next greater / next smaller element
- Histogram area
- Removing adjacent elements
- Parsing nested structures
核心思想是：
Last In, First Out
最后放进去的元素，最先被拿出来。
👉 面试回答
Stack 是一种 Last In, First Out 的数据结构。
当问题需要优先处理最近的 unresolved state 时， stack 就非常适合。
在面试中，stack 常见于括号匹配、表达式计算、DFS 模拟、nested parsing， 以及 monotonic stack 相关题，比如 next greater element 和 largest rectangle in histogram。
3️⃣ 为什么 Stack 有效？
LIFO 行为
Stack 操作：
push → 加到顶部
pop → 从顶部移除
peek → 查看顶部元素
Example:
push 1
push 2
push 3
pop → 3
pop → 2
pop → 1
为什么重要？
很多问题天然依赖最近的 unresolved item。
例如：
Opening bracket 必须匹配最近的 closing bracket。
所以：
"("
"["
"{"
最近的 opening bracket 必须先被匹配。
👉 面试回答
Stack 有效，是因为很多问题具有 nested 或 last-unresolved-first 的结构。
对括号匹配来说，最近出现的 opening bracket 必须最先被 closing bracket 匹配。
对 monotonic stack 来说，stack top 代表最近还没有找到 next greater 或 next smaller 的 candidate。
4️⃣ Valid Parentheses
Problem
判断括号字符串是否合法。
"()" → true
"()[]{}" → true
"(]" → false
"([)]" → false
"{[]}" → true
Code
def is_valid(s):
stack = []
pairs = {
")": "(",
"]": "[",
"}": "{"
}
for char in s:
if char in pairs.values():
stack.append(char)
elif char in pairs:
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return len(stack) == 0
Key Insight
遇到 closing bracket 时：
它必须匹配最近的 opening bracket。
这正好是 stack 行为。
👉 面试回答
Valid parentheses 是经典 stack 问题。
遇到 opening bracket，我把它 push 到 stack。
遇到 closing bracket，我检查它是否匹配 stack top。
如果不匹配，字符串 invalid。
最后 stack 必须为空。
5️⃣ Min Stack
Problem
设计一个 stack，支持：
push
pop
top
getMin
并且都要：
O(1)
Code
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack:
self.min_stack.append(val)
else:
self.min_stack.append(min(val, self.min_stack[-1]))
def pop(self):
self.stack.pop()
self.min_stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
Key Insight
额外维护一个 min stack。
每一层存：
到当前 depth 为止的最小值
👉 面试回答
Min Stack 可以用两个 stack 实现。
普通 stack 存正常 value。
min stack 在每一层存当前为止的 minimum value。
这样 getMin 只需要返回 min stack 的 top，就是 O(1)。
6️⃣ Remove Adjacent Duplicates
Problem
移除相邻重复字符。
"abbaca" → "ca"
Explanation:
abbaca
remove bb → aaca
remove aa → ca
Code
def remove_duplicates(s):
stack = []
for char in s:
if stack and stack[-1] == char:
stack.pop()
else:
stack.append(char)
return "".join(stack)
Key Insight
当前字符只需要和最近未解决的字符比较。
也就是：
stack[-1]
👉 面试回答
我使用 stack，因为每个新字符只需要和最近的 unresolved character 比较。
如果 stack top 和当前字符相同， 它们互相抵消。
否则，把当前字符 push 进 stack。
最后 stack 中剩下的字符组成答案。
7️⃣ Expression Evaluation
Problem Pattern
Stack 常用于表达式求值：
Reverse Polish Notation
Basic Calculator
Decode String
Nested expressions
Reverse Polish Notation Example
["2", "1", "+", "3", "*"]
表示：
(2 + 1) * 3 = 9
Code
def eval_rpn(tokens):
stack = []
for token in tokens:
if token not in {"+", "-", "*", "/"}:
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == "+":
stack.append(a + b)
elif token == "-":
stack.append(a - b)
elif token == "*":
stack.append(a * b)
else:
stack.append(int(a / b))
return stack[-1]
👉 面试回答
对 Reverse Polish Notation， 我把 operand push 到 stack。
遇到 operator 时， pop 出最近两个 operands， 计算后再 push 回 stack。
Stack 适合这个问题， 因为表达式需要优先处理最近的 operands。
8️⃣ Decode String
Problem
Decode encoded string：
"3[a]2[bc]" → "aaabcbc"
"3[a2[c]]" → "accaccacc"
Code
def decode_string(s):
stack = []
current = ""
number = 0
for char in s:
if char.isdigit():
number = number * 10 + int(char)
elif char == "[":
stack.append((current, number))
current = ""
number = 0
elif char == "]":
previous, count = stack.pop()
current = previous + current * count
else:
current += char
return current
Key Insight
Nested structure 需要记住 previous context。
Stack 存：
previous string
repeat count
👉 面试回答
Decode String 是 stack 问题，因为输入可以嵌套。
遇到 opening bracket 时， 保存当前 string 和 repeat count。
遇到 closing bracket 时， pop 出最近的 context， 并把 inner decoded string 合并回去。
Stack 帮助我们恢复最近未完成的上下文。
9️⃣ Monotonic Stack
什么是 Monotonic Stack？
Monotonic stack 维护 increasing 或 decreasing order。
用于寻找：
- Next greater element
- Next smaller element
- Previous greater element
- Previous smaller element
- Span problems
- Histogram rectangle
- Temperature waiting days
Increasing Stack
bottom → top
small → large
用于维护递增顺序，或者寻找 smaller boundary。
Decreasing Stack
bottom → top
large → small
用于维护递减顺序，或者寻找 greater boundary。
👉 面试回答
Monotonic stack 是一种保持元素单调性的 stack。
它可以是 increasing，也可以是 decreasing。
当当前元素破坏 stack 的单调性时， 我们 pop stack 中的元素，并为这些元素确定答案。
它常用于 next greater、next smaller 和 histogram 问题。
🔟 Next Greater Element
Problem
对每个元素，找到它右边第一个更大的元素。
nums = [2, 1, 2, 4, 3]
answer = [4, 2, 4, -1, -1]
Code
def next_greater_element(nums):
result = [-1] * len(nums)
stack = []
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
index = stack.pop()
result[index] = num
stack.append(i)
return result
Stack 存什么？
Stack 存还没有找到 next greater element 的 indexes。
unresolved indexes
👉 面试回答
对 next greater element， 我维护一个 decreasing stack， 里面存还没有找到答案的 index。
当当前数字大于 stack top 对应的数字时， 当前数字就是那个 index 的 next greater element。
我持续 pop，直到 stack 恢复递减顺序， 然后 push 当前 index。
1️⃣1️⃣ Daily Temperatures
Problem
对每一天，返回还要等多少天才会遇到更高温度。
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
answer = [1, 1, 4, 2, 1, 1, 0, 0]
Code
def daily_temperatures(temperatures):
result = [0] * len(temperatures)
stack = []
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
prev_index = stack.pop()
result[prev_index] = i - prev_index
stack.append(i)
return result
Pattern
这是 next greater element 的 index distance 版本。
answer[prev_index] = current_index - prev_index
👉 面试回答
Daily Temperatures 是 next greater element 问题。
我维护一个 decreasing stack， 存还没有找到 warmer day 的 indexes。
当当前温度比 stack top 的温度高时， 当前 day 就是它的 warmer day， 距离就是 current index - previous index。
1️⃣2️⃣ Online Stock Span
Problem
对于每个 stock price，返回连续多少天，包括今天，价格都小于等于今天价格。
prices = [100, 80, 60, 70, 60, 75, 85]
span = [1, 1, 1, 2, 1, 4, 6]
Code
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price):
span = 1
while self.stack and self.stack[-1][0] <= price:
_, previous_span = self.stack.pop()
span += previous_span
self.stack.append((price, span))
return span
Key Insight
Stack 中存压缩信息：
(price, span)
而不是每一天都单独存。
👉 面试回答
Stock Span 是 monotonic decreasing stack 问题。
对每个新 price， 我 pop 掉之前所有小于等于当前 price 的价格。
它们的 span 可以合并到当前 span。
这样每个 price 最多 push 一次、pop 一次， 所以 amortized O(1) per operation。
1️⃣3️⃣ Largest Rectangle in Histogram
Problem
给定 histogram heights，找最大矩形面积。
heights = [2, 1, 5, 6, 2, 3]
answer = 10
最大矩形是：
height 5 and 6
width 2
area 10
Key Insight
对每个 bar，找到左边和右边第一个更矮的 bar。
然后：
width = right_smaller_index - left_smaller_index - 1
area = height * width
Code
def largest_rectangle_area(heights):
stack = []
max_area = 0
extended = heights + [0]
for i, height in enumerate(extended):
while stack and extended[stack[-1]] > height:
h = extended[stack.pop()]
left_boundary = stack[-1] if stack else -1
width = i - left_boundary - 1
max_area = max(max_area, h * width)
stack.append(i)
return max_area
为什么加 Sentinel Zero？
最后的 0 会强制 pop 掉 stack 中剩下的所有 bars。
👉 面试回答
Largest Rectangle in Histogram 使用 monotonic increasing stack。
Stack 存 increasing height 的 indexes。
当当前 height 小于 stack top 的 height 时， 说明被 pop 的 bar 找到了右边界。
pop 之后新的 stack top 是左边界。
这样可以计算以被 pop 的 bar 作为最低高度的最大矩形。
1️⃣4️⃣ Maximal Rectangle
Problem
给定 binary matrix，找只包含 1 的最大矩形。
Key Idea
把每一行都转化成 histogram。
对于每一行：
height[c] = 当前行往上连续 1 的个数
然后套用：
largest rectangle in histogram
Code
def maximal_rectangle(matrix):
if not matrix or not matrix[0]:
return 0
rows = len(matrix)
cols = len(matrix[0])
heights = [0] * cols
best = 0
for r in range(rows):
for c in range(cols):
if matrix[r][c] == "1":
heights[c] += 1
else:
heights[c] = 0
best = max(best, largest_rectangle_area(heights))
return best
👉 面试回答
Maximal Rectangle 可以转化成 Largest Rectangle in Histogram。
对每一行，把它看成 histogram 的底部。
每个 column 的 height 表示到当前行为止连续的 1。
然后对每一行运行 histogram stack algorithm。
1️⃣5️⃣ Asteroid Collision
Problem
每个 asteroid 向左或向右移动。
正数表示向右。
负数表示向左。
两个 asteroid 碰撞时，小的爆炸。
Example
[5, 10, -5] → [5, 10]
[8, -8] → []
[10, 2, -5] → [10]
Code
def asteroid_collision(asteroids):
stack = []
for asteroid in asteroids:
alive = True
while alive and asteroid < 0 and stack and stack[-1] > 0:
if stack[-1] < -asteroid:
stack.pop()
elif stack[-1] == -asteroid:
stack.pop()
alive = False
else:
alive = False
if alive:
stack.append(asteroid)
return stack
Key Insight
只有这种情况会碰撞：
previous asteroid moving right
current asteroid moving left
也就是：
stack[-1] > 0 and asteroid < 0
👉 面试回答
Asteroid Collision 使用 stack 保存还没有被消除的 asteroids。
只有当前 asteroid 向左、stack top 向右时，才可能发生碰撞。
我不断和 stack top 解决碰撞， 直到当前 asteroid 被消除，或者不再发生碰撞。
最后 stack 中剩下的就是最终状态。
1️⃣6️⃣ Simplify Path
Problem
简化 Unix-style file path。
"/home/" → "/home"
"/../" → "/"
"/a/./b/../../c/" → "/c"
Code
def simplify_path(path):
stack = []
for part in path.split("/"):
if part == "" or part == ".":
continue
elif part == "..":
if stack:
stack.pop()
else:
stack.append(part)
return "/" + "/".join(stack)
Key Insight
Directory navigation 有 stack 行为：
folder → push
.. → pop
. → ignore
👉 面试回答
Simplify Path 是 stack 问题， 因为目录跳转具有 nested state。
普通 folder name push 到 stack。
两个点表示回到 parent directory， 所以如果 stack 不空就 pop。
一个点和空字符串可以忽略。
1️⃣7️⃣ Stack for DFS
Recursive DFS
Recursion 隐式使用 call stack。
def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
Iterative DFS
可以用 explicit stack 模拟 recursion。
def dfs_iterative(root):
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
Key Insight
Stack 存：
之后还需要处理的 nodes
👉 面试回答
DFS 天然具有 stack 行为。
Recursive DFS 使用 call stack。
Iterative DFS 使用 explicit stack 存储还需要处理的 nodes。
当我们想避免 recursion depth 问题， 或者想手动控制 traversal order 时， explicit stack 很有用。
1️⃣8️⃣ Stack vs Queue
Stack
Last In, First Out
用于：
- DFS
- Backtracking
- Matching parentheses
- Monotonic stack
- Undo
- Nested parsing
Queue
First In, First Out
用于：
- BFS
- Level-order traversal
- Shortest path in unweighted graph
- Task scheduling
Comparison
| Data Structure | Order | Common Use |
|---|---|---|
| Stack | LIFO | DFS, parsing, monotonic problems |
| Queue | FIFO | BFS, level-order traversal |
| Deque | Both ends | Sliding window max/min, BFS variants |
👉 面试回答
Stack 是 LIFO， 适合 DFS、nested parsing、括号匹配，以及处理最近 unresolved item。
Queue 是 FIFO， 适合 BFS 和 level-order processing。
选择哪一个取决于问题需要 last-in-first-out 还是 first-in-first-out。
1️⃣9️⃣ 什么时候 Stack 适用？
Good Fit
当问题有：
Nested structure
Most recent unresolved item
Need to reverse processing order
Need to simulate recursion
Need next greater or next smaller element
Need matching pairs
Need rollback or undo behavior
Problem Signals
看到这些关键词要想到 stack：
valid parentheses
next greater
previous smaller
histogram
nested
decode
simplify path
calculator
remove adjacent
DFS
👉 面试回答
当问题需要优先处理最近的 unresolved item 时， 我会考虑 stack。
常见信号包括 nested structure、matching pairs、expression evaluation、DFS traversal， 以及 next greater 或 next smaller element。
如果题目问 nearest greater / smaller， 我通常会想到 monotonic stack。
2️⃣0️⃣ 常见 Edge Cases
Empty Input
s = ""
nums = []
root = None
Empty Stack Before Pop
永远注意：
if stack:
stack.pop()
Remaining Items in Stack
最后 stack 里剩下东西要判断含义：
valid unresolved state
or
invalid input
对 parentheses：
remaining stack means invalid
对 next greater element：
remaining stack means answer is -1
Duplicates
Monotonic stack 中尤其重要：
use < or <=?
use > or >=?
这会影响 equal values 是否被 pop。
👉 面试回答
Stack 常见 edge cases 包括 empty input、 empty stack before pop、 leftover stack items， 以及 monotonic stack 中的 duplicate values。
对 monotonic stack， 我会特别注意比较条件是 strict 还是 non-strict。
2️⃣1️⃣ Complexity Analysis
Basic Stack Problems
通常是：
Time: O(n)
Space: O(n)
为什么 O(n)？
每个元素通常：
push once
pop once
所以即使有 while loop， monotonic stack 通常也是 amortized O(n)。
Example
Next greater element 中：
Each index enters the stack once.
Each index leaves the stack once.
总 work 是 linear。
👉 面试回答
大多数 stack 解法是 O(n) time 和 O(n) space。
对 monotonic stack， 虽然 for loop 里面有 while loop， 但总复杂度仍然是 amortized O(n)， 因为每个元素最多 push 一次、pop 一次。
这个 amortized analysis 在面试中要讲清楚。
2️⃣2️⃣ 常见错误
Mistake 1: 没检查 stack 是否为空就 pop
top = stack.pop()
没有：
if stack:
Mistake 2: Monotonic Direction 错误
Next greater element 通常维护：
decreasing stack
Next smaller element 通常维护：
increasing stack
Mistake 3: 该存 Index 却只存 Value
有些题需要距离或位置。
例如：
Daily Temperatures needs index distance.
所以应该存 index，而不是只存 value。
Mistake 4: Equal Values 处理错误
比较符号很重要：
<
<=
>
>=
Mistake 5: 没解释 Amortized O(n)
Nested while loop 看起来像 O(n²)，但每个元素最多 pop 一次。
👉 面试回答
常见错误包括： pop 前不检查 stack 是否为空、 monotonic direction 搞反、 需要 index 却只存 value、 equal values 处理错误、 以及没有解释 amortized O(n)。
我通常会先定义 stack 存什么， 以及它维护什么 invariant。
2️⃣3️⃣ 标准模板
Basic Stack Template
stack = []
for item in items:
if should_push(item):
stack.append(item)
else:
if not stack:
return invalid
top = stack.pop()
process(top, item)
Parentheses Template
def is_valid(s):
stack = []
pairs = {")": "(", "]": "[", "}": "{"}
for char in s:
if char in pairs.values():
stack.append(char)
elif char in pairs:
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return not stack
Monotonic Stack Template
stack = []
result = [-1] * len(nums)
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
index = stack.pop()
result[index] = num
stack.append(i)
Histogram Template
def largest_rectangle_area(heights):
stack = []
max_area = 0
extended = heights + [0]
for i, height in enumerate(extended):
while stack and extended[stack[-1]] > height:
h = extended[stack.pop()]
left = stack[-1] if stack else -1
width = i - left - 1
max_area = max(max_area, h * width)
stack.append(i)
return max_area
Iterative DFS Template
def dfs_iterative(root):
if not root:
return []
stack = [root]
result = []
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
🧠 Staff-Level Answer Final
👉 面试回答完整版本
Stack 是一种 Last In, First Out 的数据结构。
它适合处理最近出现、但还没有解决的问题。
这种模式常见于 parentheses matching、expression evaluation、nested parsing、DFS traversal、undo behavior， 以及 monotonic stack 问题。
对 valid parentheses， stack 存 unmatched opening brackets。 当 closing bracket 出现时， 它必须匹配 stack top 的 opening bracket。 如果不匹配，输入 invalid。
对 expression evaluation， stack 可以存 operands 或 previous parsing context。 在 Reverse Polish Notation 中， 遇到 operator 时， pop 出最近两个 operands， 计算后再 push 回 stack。
对 Decode String 这类 nested parsing 问题， stack 存 previous context。 进入 bracket 时保存当前 string 和 repeat count。 关闭 bracket 时恢复 context， 并合并 decoded inner string。
一个重要面试模式是 monotonic stack。 Monotonic stack 维护 increasing 或 decreasing order。 它常用于 next greater element、daily temperatures、stock span 和 largest rectangle in histogram。
核心思想是： 当当前元素破坏 stack 的单调性时， 我们 pop stack 中 unresolved elements， 并为这些元素确定答案。
对 next greater element， stack 通常存 decreasing value order 的 indexes。 当当前 value 大于 stack top 对应的 value 时， 当前 value 就是那个 index 的 next greater element。
对 largest rectangle in histogram， 我使用 monotonic increasing stack。 当当前 height 更小时， 被 pop 的 bar 找到了右边界。 新的 stack top 是左边界。 这样就可以计算以被 pop bar 作为 limiting height 的最大矩形。
Stack 也和 DFS 密切相关。 Recursive DFS 隐式使用 call stack。 Iterative DFS 使用 explicit stack。
高级工程师解释 stack pattern 时， 我会讲清楚： stack 中存什么， stack 维护什么 invariant， 什么时候 push， 什么时候 pop， 以及 pop 出来的元素代表什么问题被解决了。
大多数 stack 算法是 O(n) time 和 O(n) space。 对 monotonic stack， 即使代码里有 nested while loop， 总复杂度仍然是 amortized O(n)， 因为每个元素最多 push 一次、pop 一次。
主要陷阱包括： empty stack error、 该存 index 却存 value、 monotonic direction 搞反、 equal values 处理错误、 以及没有解释 stack invariant。
⭐ Final Insight
Stack Patterns 的核心不是 append 和 pop。
它的核心是处理 most recent unresolved state。
Senior-level 的重点是：
stack 里存什么， stack 维护什么 invariant， 什么时候 push， 什么时候 pop， pop 出来的元素代表什么问题被解决了。
对 monotonic stack， 还要讲清楚为什么 nested while loop 仍然是 amortized O(n)。
能讲清楚这些， Stack 就是一类处理 nested state、unresolved candidates 和 nearest boundary 的通用算法模式。
Implement