算法模板
模板不是用来背诵的，而是帮你在高压做题时快速把“状态、不变量、边界”搭起来。
🧭 模板怎么读
模板不是背代码，而是记住三个问题：
- 这个模板维护了什么不变量：例如二分维护“答案仍在搜索区间里”，单调栈维护“栈内元素保持单调”。
- 每次循环排除了什么：被排除的区间、元素或状态以后不会再成为答案。
- 边界为什么这样写：循环条件、遍历方向、初始化值都要服务于不变量。
flowchart LR A[识别题型] --> B[选择模板] B --> C[确认状态与不变量] C --> D[调整输入输出] D --> E[用边界样例验证]
基础算法模板
查找与遍历
数据结构模板
栈和队列
高级数据结构
- 并查集模板 - 路径压缩、按秩合并、带权并查集
- 堆（优先队列）模板 - TopK问题
- Trie树模板 - 前缀匹配
- 线段树模板 - 区间查询、单点修改、懒标记
- 树状数组模板 - 前缀统计、逆序对、动态区间和
搜索算法模板
详见 搜索算法：
动态规划模板
经典DP
- 背包问题模板 - 0-1背包、完全背包、多重背包、分组背包
其他DP
图算法模板
最短路径
- 最短路径模板 - Dijkstra、Bellman-Ford、Floyd、SPFA
其他图算法
- 拓扑排序模板 - 课程表
- 最小生成树模板 - Kruskal、Prim
- 0-1 BFS模板 - 边权只有0和1的最短路
- 二分图匹配模板 - Hopcroft-Karp
- Tarjan模板 - 强连通分量、割点、桥
字符串算法模板
- KMP模板 - 字符串匹配
- Rabin-Karp模板 - 滚动哈希
- Z Algorithm模板 - 字符串匹配与前缀比较
- Manacher模板 - 最长回文子串
- AC自动机模板 - 多模式串匹配
怎么用模板
先识别题型
| 关键词 | 对应模板 |
|---|---|
| 有序数组、查找 | 二分查找 |
| 两数之和、回文 | 双指针 |
| 子串、子数组 | 滑动窗口 |
| 区间和、矩形和 | 前缀和 |
| 下一个更大 | 单调栈 |
| 连通性、合并 | 并查集 |
| 最大价值、装满 | 背包问题 |
| 最短路径 | 图算法 |
| 只有0/1边权 | 0-1 BFS |
| 多模式匹配 | AC自动机 |
| 区间修改查询 | 线段树 |
| 动态前缀和 | 树状数组 |
再按这个顺序套
- 找到最接近的模板。
- 先确认模板维护了什么不变量。
- 再改初始化、循环边界和返回值。
- 最后用最小样例和边界样例验证。
常见陷阱
| 模板 | 易错点 | 正确做法 |
|---|---|---|
| 二分查找 | 边界条件 | 统一区间定义 |
| 滑动窗口 | 窗口何时收缩 | 明确收缩条件 |
| 单调栈 | 栈存值还是索引 | 通常存索引 |
| 背包问题 | 遍历顺序 | 0-1后向前，完全前向后 |
| 并查集 | 忘记路径压缩 | find时压缩 |
优先掌握顺序
- 先吃透二分、双指针、滑动窗口、前缀和。
- 再掌握单调栈、堆、并查集。
- 然后补 DFS、BFS、回溯、背包。
- 最后看图算法和字符串算法的专项模板。
已完成模板
- 二分查找模板（4种）
- 双指针模板（4种）
- 滑动窗口模板（4种）
- 前缀和模板（4种）
- 单调栈模板
- 并查集模板（3种）
- 背包问题模板（4种）
- 最短路径模板（4种）
- 单调队列模板
- 堆与双堆模板
- Trie树模板
- 线段树模板
- 树状数组模板
- DFS模板
- BFS模板
- 回溯模板
- LCS/LIS模板
- 区间DP模板
- 树形DP模板
- 状态压缩DP模板
- 数位DP模板
- 拓扑排序模板
- 最小生成树模板
- 0-1 BFS模板
- 二分图匹配模板
- Tarjan模板
- KMP模板
- Rabin-Karp模板
- Z算法模板
- Manacher模板
- AC自动机模板
相关主题
返回：算法学习导航