✅ 必做 LeetCode 栈题清单(高频 + 分类清晰)
🟢 简单(适合入门理解栈基本用法)
题号 | 题目 | 类型 |
---|---|---|
20 | Valid Parentheses | 括号匹配 |
155 | Min Stack | 设计栈(带辅助栈) |
232 | Implement Queue using Stacks | 栈模拟队列 |
225 | Implement Stack using Queues | 队列模拟栈 |
1047 | Remove All Adjacent Duplicates In String | 字符串栈消除 |
🟡 中等(面试高频,涉及单调栈、表达式计算等)
题号 | 题目 | 类型 |
---|---|---|
150 | Evaluate Reverse Polish Notation | 后缀表达式(逆波兰)求值 |
739 | Daily Temperatures | 单调栈 |
853 | Car Fleet | 单调栈+排序 |
901 | Online Stock Span | 单调栈 |
316 | Remove Duplicate Letters | 单调栈+贪心 |
1021 | Remove Outermost Parentheses | 括号匹配 |
856 | Score of Parentheses | 栈模拟嵌套评分 |
84 | Largest Rectangle in Histogram | 单调栈经典题 |
🔴 困难(偏算法设计)
题号 | 题目 | 类型 |
---|---|---|
85 | Maximal Rectangle | 单调栈 + 动态规划 |
224 | Basic Calculator | 表达式求值 |
227 | Basic Calculator II | 表达式求值(中缀) |
772 | Basic Calculator III | 括号嵌套表达式 |
84 | Largest Rectangle in Histogram | 核心单调栈模板题 |
📌 推荐刷题顺序(学习路径)
1. 栈的基本操作 → [20]、[155]
2. 栈模拟其他结构 → [225]、[232]
3. 表达式求值 → [150]、[224]、[227]
4. 单调栈基础 → [739]、[901]
5. 单调栈进阶 → [84]、[85]
6. 贪心 + 单调栈 → [316]
7. 括号相关技巧 → [1021]、[856]
📚 拓展(含栈的 DFS/递归模拟类)
- [144. Binary Tree Preorder Traversal] – 栈实现前序遍历
- [145. Binary Tree Postorder Traversal] – 栈实现后序
- [94. Inorder Traversal] – 中序遍历迭代实现
当然可以!
✅ 1. Stack 实现 in Python
class Stack:
def __init__(self):
self.stack = []
def push(self, val):
self.stack.append(val)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.stack.pop()
def top(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.stack[-1]
def is_empty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)
✅ 2. Classic Stack-Based Algorithms (in Pseudocode, English)
📌 A. Valid Parentheses (LeetCode 20)
Goal: Check if all parentheses/brackets are matched correctly.
Initialize an empty stack
For each character c in input string:
If c is an opening bracket:
Push c to the stack
Else if c is a closing bracket:
If stack is empty:
Return false
Pop from the stack
If popped value does not match c:
Return false
Return true if stack is empty, else false
📌 B. Evaluate Reverse Polish Notation (LeetCode 150)
Goal: Evaluate an expression like ["2", "1", "+", "3", "*"] → (2 + 1) * 3
Initialize an empty stack
For each token in the expression:
If token is a number:
Push it to the stack
Else:
Pop two elements from the stack
Apply the operation: second operand op first operand
Push the result back to the stack
Return the top of the stack
📌 C. Daily Temperatures (LeetCode 739) – Monotonic Stack
Goal: For each day, find out how many days until a warmer temperature.
Initialize an empty stack to store indices
Initialize an array result of size n with all 0s
For i from 0 to n-1:
While stack is not empty and temperatures[i] > temperatures[stack.top()]:
index = stack.pop()
result[index] = i - index
Push i to stack
Return result
📌 D. Largest Rectangle in Histogram (LeetCode 84)
Append 0 to the end of heights to flush stack
Initialize empty stack and max_area = 0
For i in 0 to len(heights):
While stack is not empty and heights[i] < heights[stack.top()]:
height = heights[stack.pop()]
width = i if stack is empty else i - stack.top() - 1
max_area = max(max_area, height * width)
Push i to stack
Return max_area
📌 E. Min Stack (LeetCode 155) – Stack with O(1) min
Use two stacks:
- mainStack for normal values
- minStack to track the minimum
push(x):
Push x to mainStack
If minStack is empty or x <= minStack.top():
Push x to minStack
pop():
If mainStack.pop() == minStack.top():
minStack.pop()
getMin():
Return minStack.top()
Top comments (0)