数据结构 (Data Structures for LeetCode)
在做 LeetCode 算法题时，选择合适的数据结构往往能让解题事半功倍。Python 标准库提供了许多高性能的数据结构，熟练掌握它们是刷题的关键。
1. 列表 (List) 作为 栈 (Stack)
Python 的列表本质上是动态数组，但在尾部添加和删除元素的时间复杂度都是 O(1)，因此非常适合用作栈（后进先出 LIFO）。
常用操作
- 入栈:
stack.append(val) - 出栈:
stack.pop() - 查看栈顶:
stack[-1] - 判空:
if not stack:
stack = []
stack.append(1)
stack.append(2)
print(stack.pop()) # 2
2. 双端队列 (Deque)
collections.deque 是双端队列，支持在两端以 O(1) 的复杂度添加和删除元素。它不仅可以作为栈使用，更常用作队列（先进先出 FIFO）。
常用操作
- 引入:
from collections import deque - 入队:
queue.append(val) - 出队:
queue.popleft()(注意不是 pop，pop 是移除右端) - 双向操作:
appendleft(),pop()
from collections import deque
queue = deque([1, 2, 3])
queue.append(4) # [1, 2, 3, 4]
val = queue.popleft() # 1, 剩下 [2, 3, 4]
3. 堆 (Heap) / 优先队列
Python 的 heapq 模块提供了小顶堆（Min Heap）的实现。对于 Top K 问题、合并 K 个有序链表等非常有用。
常用操作
- 引入:
import heapq - 建堆:
heapq.heapify(list)(O(n)) - 推入:
heapq.heappush(heap, val)(O(log n)) - 弹出:
heapq.heappop(heap)(O(log n), 弹出最小值) - 访问最小值:
heap[0]
import heapq
nums = [3, 1, 4, 1, 5, 9]
heapq.heapify(nums) # 注意：这是原地修改 (In-place)，nums 列表本身变成了堆结构
print(heapq.heappop(nums)) # 1 (最小值)
heapq.heappush(nums, 2)
为什么不赋值给变量？
heapq.heapify(x) 是原地修改操作，它直接改变了列表 x 的内部顺序以满足堆的性质，并返回 None。
❌ 错误写法：my_heap = heapq.heapify(nums) （这样 my_heap 是 None）
✅ 正确写法：直接把 nums 当作堆来传参，如 heapq.heappush(nums, 2)。
堆的底层实现
你的理解非常到位！Python 的堆并不是一个新的数据类型，它本质上就是一个普通的列表 (List)。
heapq 模块只是提供了一组函数（算法），按照二叉堆的规则来操作这个列表，保证列表满足 heap[k] <= heap[2*k+1] 和 heap[2*k+2] 的性质。
这意味着：
1. 你不需要创建一个特殊的 Heap 对象。
2. heap[0] 永远是堆顶（最小值）。
3. 你可以随时 print(heap) 查看它的内部状态。
如果要用大顶堆怎么办？
Python 没有内置大顶堆。技巧是存储元素的相反数（负数）。例如存 -num，这样最小的负数其实就是最大的正数。取出时再取反即可。
4. 默认字典 (DefaultDict)
collections.defaultdict 在访问不存在的键时，会自动赋予一个默认值，避免了 Key Error 的判断。在图论（构建邻接表）和计数问题中非常常用。
常用示例
from collections import defaultdict
# 1. 计数：默认值为 0
count = defaultdict(int)
s = "banana"
for char in s:
count[char] += 1
print(count) # {'b': 1, 'a': 3, 'n': 2}
# 2. 列表归类：默认值为 []
groups = defaultdict(list)
groups['even'].append(2)
groups['odd'].append(1)
print(groups)
# 输出: defaultdict(<class 'list'>, {'even': [2], 'odd': [1]})
# 效果：直接 append 即可，不用判断 key 是否存在，也不用手动初始化为空列表。
5. 计数器 (Counter)
collections.Counter 是专门用于计数的字典子类，比手动循环计数更简洁高效。
常用操作
- 统计词频:
Counter(iterable) - 获取最常见的元素:
most_common(k)
from collections import Counter
nums = [1, 1, 1, 2, 2, 3]
counts = Counter(nums)
print(counts) # Counter({1: 3, 2: 2, 3: 1})
# 获取出现次数最多的前 2 个元素
print(counts.most_common(2)) # [(1, 3), (2, 2)]
总结
| 数据结构 | 适用场景 | Python 实现 | 关键方法 |
|---|---|---|---|
| 栈 | 括号匹配、DFS | list |
append, pop |
| 队列 | BFS、层序遍历 | collections.deque |
append, popleft |
| 堆 | Top K、优先级调度 | heapq |
heappush, heappop |
| 哈希表 | 快速查找、去重 | dict, set |
in, get |
| 计数器 | 词频统计 | collections.Counter |
most_common |
熟练掌握 deque, heapq 和 defaultdict/Counter，能极大提升刷题效率和代码简洁度。
下一步
随着代码规模的增长，我们将无法再把所有代码都塞进一个文件里。这时就需要引入“分而治之”的思想，利用模块和包来组织代码结构。