栈 / 队列 / 哈希

这一分类以栈、队列和哈希表的典型题为主，同时收录几道常见的字符串、回溯和数位计数题。

算法模板

题目核心方法关键点
1. 两数之和哈希表用空间换时间，保存已遍历元素
20. 有效的括号栈最近出现的左括号最先匹配
907. 子数组的最小值之和单调栈 + 贡献法计算每个元素作为最小值时覆盖的子数组数量
232. 用栈实现队列双栈输入栈负责写入，输出栈负责读取
146. LRU 缓存哈希表 + 双向链表同时实现 O(1) 定位、移动和淘汰
415. 字符串相加双指针 + 模拟从低位向高位逐位相加
165. 比较版本号双指针 / 分割逐段比较修订号
46. 全排列回溯路径、选择列表、撤销选择
902. 最大为 N 的数字组合数位计数统计短位数，再处理与 n 等长的前缀

三种数据结构的判断信号

  • 需要“后进先出”、括号匹配、表达式求值或单调关系时，考虑栈。
  • 需要“先进先出”、层序遍历或任务排队时，考虑队列。
  • 需要快速判断是否出现过、建立值到位置的映射或 O(1) 定位节点时，考虑哈希表。

数据结构只是工具。做题时应先识别问题需要维护的状态和操作复杂度，再决定使用哪种结构。