刷题必备：单调栈、单调队列、并查集、字符串哈希与Trie树模板总结

刷题刷到一定量之后，很多人会有一种感觉：单看某道题，解法大概知道，但一到组合题就抓瞎。突然遇到“下一段区间里找最大值”“动态维护一堆点的连通关系”“判断两个子串是否相同”“给一堆单词找公共前缀”，这几类问题，本质上都逃不开今天要写的五块内容：单调栈、单调队列、并查集、字符串哈希、Trie树。

这篇文章就是一份可收藏的习题集锦式总结。每一块我都会先讲清楚“它到底在解决什么问题”，再给一份可以直接抄的C++模板，然后配上一到两道有代表性的题目拆解，最后把我踩过的坑单独列出来。不管你是在准备校招笔试、打算法竞赛，还是单纯想把基础数据结构补扎实，按这个顺序刷下来，收获会比较直观。

1. 单调栈：解决“下一个更大元素”的利器

1.1 单调栈是什么，为什么它好使

很多初学者第一次见单调栈，会觉得它不过是“栈里元素保持单调”而已，学完了照样不知道什么时候用。我的理解是这样的：单调栈核心解决一类问题，找到每个元素左侧或右侧第一个大于/小于它的位置，这个“第一个”非常关键。

先看最经典的“下一个更大元素”问题：给一个数组，求每个元素右边第一个比它大的数。朴素做法是两重循环，O(n^2)。单调栈的做法是维护一个从栈底到栈顶单调递减的栈，遍历数组时，如果当前元素比栈顶大，就一直弹出栈顶。被弹出的元素是什么时候确定答案的？就是现在。当前这个元素就是“右边第一个比它大的数”。

这里有一个很形象的类比：想象一排人从矮到高站成一条线，你从队伍左边往右边看，一个更高的新来者会把前面所有比他矮的人“挡住”。被挡住的人出栈那一刻，就等于是“看到了右边第一个比他高的人”。这个类比能帮你把单调栈的直觉刻在脑子里。

单调栈的价值在于每个元素最多入栈一次、出栈一次，所以总复杂度是O(n)。它把二维枚举的“每个元素向后找”优化成了一个扫描过程。

1.2 柱状图中最大矩形：单调栈典中典

题目是这样的：给一个非负整数数组heights，每个数代表一根柱子的高度，求这些柱子能围成的最大矩形面积。典型样例是 heights = [2,1,5,6,2,3]，答案应该是10。

朴素思路是枚举每一根柱子作为矩形的高度，然后向左右扩展，直到遇到比它矮的柱子为止。这样每一根柱子都要向两边扫一遍，最坏O(n^2)。单调栈的版本思路完全一样，但左右边界都用栈一次算出来。

核心逻辑：维护一个高度单调递增的栈（栈底到栈顶递增）。遍历柱子 i 时，只要 heights[i] 小于等于栈顶柱子的高度，就说明栈顶柱子的右边界已经出现，弹出栈顶，以它为矩形的高，计算面积。弹出后新的栈顶柱子高度一定比弹出的柱子矮，所以它就是左边界。面积公式就是：

面积 = 高度 * (i - 左边界下标 - 1)

为了让最后栈里所有柱子都完成计算，可以在数组头尾各加一个高度为0的哨兵。左边哨兵保证栈不会空，右边哨兵强制所有柱子出栈。模板如下：

int largestRectangleArea(vector<int>& heights) { int n = heights.size(); vector<int> h(n + 2, 0); for (int i = 1; i <= n; i++) h[i] = heights[i - 1]; vector<int> st(n + 2); int top = -1; st[++top] = 0; // 左哨兵入栈 int ans = 0; for (int i = 1; i <= n + 1; i++) { while (top > 0 && h[st[top]] >= h[i]) { int height = h[st[top]]; top--; int width = i - st[top] - 1; // 右边界 i，左边界 st[top] ans = max(ans, height * width); } st[++top] = i; } return ans; }

每次弹出时，h[st[top]]是当前以它为高度的矩形的高，i是右边第一个不高于它的位置，st[top]弹出后的栈顶是左边第一个矮于它的位置。宽度就是这两根边界柱子之间的距离。哨兵的存在让你完全不用特判栈为空的情况，代码会干净很多。

这个题如果你能自己推导出来，单调栈基本就入门了。它的经典变形也很多：“每日温度”求右边第一个更暖的天距离几天，其实也是同一个模板，只是把面积改成下标差；“接雨水”需要维护两个方向的最大值，但思路有交叉。

1.3 单调栈实战中的三个注意点

第一，哨兵不要省。不加哨兵的话，你需要在循环结束后把栈里剩余元素全部弹出来再算一遍，而且中途还要特判栈空。加了哨兵之后，代码逻辑统一，出错概率大幅下降。

第二，相等元素怎么处理。我建议在维护严格单调性的情况下，遇到相等也弹出。比如柱状图那道题，如果遇到相等不弹，那么右边界定义是“第一个不高于”，左边界定义是“第一个严格小于”，左右不对称用起来很绕。用>=弹出，虽然相等的柱子也会被弹出，但每个元素仍然只入栈出栈一次，复杂度不会退化，而且面积覆盖是完整的。

第三，实际写代码推荐用数组模拟栈，而不是STL的stack。原因很简单：数组直接按下标访问，能快速拿到左边界位置；STL stack只能访问栈顶，一旦元素弹出就丢了信息，调试起来也不直观。这类题目里的“栈”更准确的说是保存下标的一个序列，数组模拟刚好满足。

2. 单调队列：滑动窗口里的常驻冠军

2.1 从“滑动窗口最大值”理解单调队列

单调队列解决的问题也很集中：一个固定大小的窗口向右滑动，每次窗口里的最大值（或最小值）是多少。如果你每次都遍历窗口，复杂度O(nk)，当n和k都到10^5级别时肯定超时。

为什么队列能维护这个最大值？因为窗口滑动时，左边要出元素，右边要进元素，天然符合队列的先进先出结构。单调队列在普通队列基础上加了一条规则：从队头到队尾，元素对应的值保持单调递减（求最大值的情况）。

关键逻辑有两个：

• 新元素从队尾进入前，把队尾所有比它小的元素全部弹出。因为新元素更靠右，在窗口里存活时间更长，且值更大，那些比它小的旧元素以后再也没有机会成为最大值。
• 队头如果已经滑出窗口左边界，直接从队头弹出。

你可能会问：为什么用双端队列而不是普通队列？因为不仅要队头出，还要队尾出，普通队列做不到。

这里有一个重要细节：队列里存的是数组下标，不是值。下标能让你判断“这个元素还在不在当前窗口内”。如果只存值，你无法知道它是否过期。

2.2 手写版本模板，比deque更快更稳

虽然C++的deque能直接实现双端操作，但竞赛和笔试里我一般手写数组模拟。一方面是常数小，另一方面是逻辑更清楚，不容易写着写着忘记维护单调性。

const int MAXN = 1000005; int a[MAXN], q[MAXN]; // q 存下标 int hh = 0, tt = -1; for (int i = 1; i <= n; i++) { // 1. 淘汰过期队头 if (hh <= tt && q[hh] <= i - k) hh++; // 2. 维护单调性（求最大值，队头到队尾递减） while (hh <= tt && a[q[tt]] <= a[i]) tt--; // 3. 入队 q[++tt] = i; // 4. 窗口完整时记录答案 if (i >= k) cout << a[q[hh]] << " "; }

这里淘汰条件为什么是q[hh] <= i - k而不是< i - k？因为窗口范围是[i - k + 1, i]，下标i - k已经不在窗口内了。比如 k=3，i=5时窗口是[3,5]，下标2就过期了，刚好满足2 <= 5-3。这个细节写错，第一眼看不出问题，数据一大就错。

时间复杂度O(n)，空间O(k)。每个下标最多入队一次、出队一次，这是单调队列复杂度永远为线性的关键。

2.3 重头戏：用单调队列优化DP

“单调队列优化DP”是近几年笔试和比赛中出现频率很高的考点。它的使用场景很典型：状态转移方程里的决策变量落在一个固定长度区间内，即

dp[i] = max( dp[j] ) + cost[i], 其中 j ∈ [i - k, i - 1]

如果每次枚举j，复杂度O(nk)；但max(dp[j])本质上就是一个滑动窗口最大值，完全可以用单调队列O(1)拿到。

举一个非常经典的例子：一条赛道有n个站点，你在站点0出发，每次最多跳k步，到达站点i会得到val[i]分，求到达站点n能拿到的最大分数。状态转移是：

dp[i] = max(dp[j]) + val[i], j ∈ [i - k, i - 1]

朴素版本是每一个i都回看前k个dp值，总复杂度O(nk)。k一大直接吃满超时。

单调队列优化版本：

int dp[MAXN], q[MAXN]; int hh = 0, tt = -1; dp[0] = val[0]; for (int i = 1; i <= n; i++) { // 先让 i-1 成为候选决策 while (hh <= tt && dp[q[tt]] <= dp[i - 1]) tt--; q[++tt] = i - 1; // 淘汰过期决策 if (hh <= tt && q[hh] < i - k) hh++; // 队头就是最优转移来源 dp[i] = dp[q[hh]] + val[i]; }

注意这里我在加入候选和取最大值的时候稍微调换了顺序：因为当前轮可以用的决策范围是[i-k, i-1]，而i-1正好是这一轮才变成合法的决策，所以要先把它放进队列，再淘汰过期元素，最后取队头。这个顺序如果理解不到位，写出来的代码总是差一点。

优化之后每个状态只入队出队一次，总复杂度O(n)。从O(nk)到O(n)，这是指数级别的差距，很多题能不能过全看这一步。

单调队列优化DP还有一个常见变形：dp[i] = min(dp[j] + cost(i, j))且转移区间约束固定。比如多重背包的优化，也可以用单调队列把O(NV)降到O(NV)但去掉掉内层枚举个数？具体是多重背包朴素O(NVK)，用单调队列可以做到O(N*V)，思路是把余数分组。这个模型在面试和竞赛里出现频率很高，建议单独研究一下。

3. 并查集：把“关系”归类的万能胶水

3.1 并查集主要用来做什么？一句话说清

很多初学者被“并查集”这个名字带偏，以为它侧重“查找”。实际上它最核心的能力是：动态维护若干个不相交集合，支持合并两个集合、查询两个元素是否在同一个集合中。不是查值，是查“归属”。

生活类比就是：你有一个班级名单，刚开始每个人自己成一派。如果两个人是同桌，就把他们两派合并；过一会儿有人问你A和B是不是同桌派系里的人，你只需要看他们所属的“派系代表”是不是同一个人。

典型应用场景：

• 无向图里判断两个点是否连通、动态合并连通块。
• Kruskal最小生成树算法里合并点时避免成环。
• 维护类似于“a和b是亲戚”“a和b是队友”的关系约束。
• 离线处理删边问题，把删除操作倒过来变成加边。

一句话：并查集是处理“动态连通性”的基础数据结构。

3.2 模板工程：路径压缩和按秩合并

并查集模板代码很短，但要写出健壮版本，有两个优化必须掌握。

第一个是路径压缩。find操作时，把查找路径上的所有节点直接挂到根节点上，这样下一次查找几乎O(1)。第二个是按秩合并，合并时让高度低的树挂到高度高的树下，防止退化成长链。

实际工程里我常把“秩”直接复用为集合大小，这样不仅维护了树高，还顺手得到每个集合的元素个数，一举两得：

const int MAXN = 100005; int fa[MAXN], sz[MAXN]; void init(int n) { for (int i = 1; i <= n; i++) { fa[i] = i; sz[i] = 1; } } int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; // 隔代压缩 x = fa[x]; } return x; } void merge(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return; if (sz[ra] < sz[rb]) swap(ra, rb); fa[rb] = ra; sz[ra] += sz[rb]; }

这里我用的是迭代写法，比递归版少一点爆栈风险。同时注意merge里先find再判断，不要把find结果直接用没压缩的父节点。

路径压缩之后，find的均摊复杂度接近反阿克曼函数，可以认为是常数级。也就是说，你不用太担心并查集在大数据量下变慢。

3.3 带权并查集：不止分阵营，还要算距离

并查集还能再进一步，维护节点到根节点的“权值”。这种模型叫带权并查集，或者向量偏移并查集，最经典的题目是“食物链”。题里动物之间不止“是否同类”，还有捕食关系，这时就需要额外维护一个模数关系。

假设权值数组d[x]表示x到其父节点的偏移量，取模p。find时除了路径压缩，还需要顺带更新权值：

int find(int x) { if (fa[x] == x) return x; int root = find(fa[x]); d[x] = (d[x] + d[fa[x]]) % p; return fa[x] = root; }

合并两个集合时，已知x和y之间的关系c，要计算两个根之间的偏移量。公式是：

fa[rx] = ry; d[rx] = (c + d[y] - d[x] + p) % p;

这里的推导思路是向量加减：x -> y 的偏移 = x -> rx + rx -> ry + ry -> y，移项得到根之间的偏移量。这类题复杂一点，但只要把“每一条关系都表示成偏移量”这个思维建立起来，套路就很固定。

带权并查集常见的坑：

• find递归时，先存旧父节点，再更新权值，再赋值根节点。顺序写错，权值就全乱了。
• 合并公式里的符号容易搞反，建议自己画三四个点推一遍再记忆。
• 取模后结果是负的，记得加模数调整。

3.4 并查集的扩展套路：反集与离线倒序

除了基础模板，还有两个高频扩展套路值得记下来。

反集一般用于处理“矛盾关系”。比如题目要求“a和b不能在同一个集合”，你可以给每个人开一个虚拟对立节点，合并操作时把a和b的对立节点合并、b和a的对立节点合并。判断有没有矛盾时，看a和b是否已经在同一集合，如果是就说明要求冲突了。

离线倒序处理是应对“删边”类题目的经典手法。图的删边操作不好维护连通性，但加边操作很容易。处理办法是把所有询问离线读进来，从最终状态开始，把删除操作倒序看成加边操作。一套并查集跑完，再把答案倒序输出。这个技巧在历年很多省赛题里出现过。

4. 字符串哈希：两条串相等的O(1)判断

4.1 把字符串映射成一个数字

字符串哈希的核心思路很简单：把一个字符串整个变成一个整数，这样判断两个字符串是否相等，就变成了判断两个整数是否相等，复杂度从O(len)降到O(1)。

最常用的滚动哈希公式是这样的：

h[i] = (h[i-1] * base + s[i]) % mod

预处理出前缀哈希h[i]，再用幂次数组pow[i] = base^i % mod，就可以O(1)取任意子串s[l..r]的哈希值：

hash(l, r) = (h[r] - h[l-1] * pow[r-l+1] % mod + mod) % mod

这个公式的直觉是：h[r]相当于把s[0..r]编码成一个数字，h[l-1] * pow[r-l+1]是把s[0..l-1]部分左移到对齐的位置，减掉之后剩下的就是s[l..r]对应的编码。

base的选择很关键。常用的是131、13331、137，这些经验值是从竞赛实践里沉淀出来的，不要乱选。base要大于字符集大小，否则碰撞概率会显著增加。模数常用1e9+7或1e9+9，也可以直接用模2^64。

4.2 自然溢出和双哈希到底怎么选

字符串哈希有一个绕不开的问题：哈希碰撞。两个不同的串可能哈希值相同，导致误判相等。

C++里最省事的方式是用unsigned long long自然溢出，等价于模2^64。因为溢出自动取模，不需要手动取模，速度非常快。代价是，恶意构造的数据可以针对性卡掉单哈希，碰撞概率虽然低但不是零。

更稳的方案是双哈希：用两组不同的base和mod算两次哈希，把两个哈希值组合成一个pair比较。碰撞概率低到可以忽略，代价是多一倍的预处理时间和内存。

我的建议是：日常刷题用单哈希 + 大质数模数基本够用；比赛时如果题目允许随机化，可以随机选base来防卡；在人生关键的大规模数据题目上，不要省那一倍的常数，直接上双哈希。字符串哈希最怕的就是“看起来过了，但其实靠运气”，遇到构造数据会直接翻车。

4.3 字符串哈希完整模板与典型应用

#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007; const long long BASE = 131; long long h[1000005], powv[1000005]; void init(const string& s) { int n = s.size() - 1; // s[0] 是哨兵，从 1 开始存 powv[0] = 1; for (int i = 1; i <= n; i++) { h[i] = (h[i - 1] * BASE + s[i]) % MOD; powv[i] = powv[i - 1] * BASE % MOD; } } long long getHash(int l, int r) { return (h[r] - h[l - 1] * powv[r - l + 1] % MOD + MOD) % MOD; }

使用的时候字符串下标从1开始，否则公式里l-1会出问题。这里一个常见错误是忘记把乘出来的结果先取模再减，导致中间结果溢出到负数，最后取模出来是错值。

典型应用之一是统计长度为L的不同子串个数：把所有子串哈希塞进set，去重后输出size。这题如果用map直接比较字符串，复杂度O(nL)，哈希做法O(nL)预处理加O(n)枚举，提升明显。

另一个经典应用是最长回文子串。预处理正串和反串的哈希，二分回文半径，每次O(1)判断左右对应的子串是否相等，整体复杂度O(n log n)。比马拉车写法简单很多，即使不是最优复杂度，笔试现场能快速写对才是王道。

5. Trie树：把前缀刻进树里

5.1 先纠正一个笔误：Tire还是Trie

好多题解里会写成“Tire树”，比如很多标题就是这么写的。正确拼写是Trie，读作“try”，来源于retrieval（检索）。它也叫字典树、前缀树。名字虽然有点小岔子，但核心思想非常清晰：用一棵多叉树把多个字符串的前缀重叠存储起来，公共前缀只存一份。

你在一个Trie里插入"apple"和"apply"时，前四个字符"appl"是共享一条链的，到第五个字符才分叉。这样既省空间，又能非常自然地做前缀匹配、前缀计数、字典序排序等操作。

为什么用树？因为本质上我们在处理前缀关系，树恰好把“前缀相同”表示成“同一个父节点路径”，这是数组或哈希表做不到的表达。

5.2 为什么我推荐用静态数组实现

网上很多教程教你用指针动态建树：

struct Node { Node* child[26]; int cnt; };

这种写法理解起来直观，但实际竞赛或笔试中，我强烈推荐用二维数组实现。原因有三个：第一，避免指针申请和释放的开销，内存更可控；第二，数组下标天然就是节点的“指针”，调试时能直接打出下标；第三，不会出现漏写delete导致内存泄漏的问题。

静态数组模板：

const int MAX_NODE = 1000000; int trie[MAX_NODE][26]; int cnt[MAX_NODE]; int tot = 0; // 当前节点总数，0 表示根节点 void insert(const string& s) { int p = 0; for (char c : s) { int id = c - 'a'; if (trie[p][id] == 0) trie[p][id] = ++tot; p = trie[p][id]; } cnt[p]++; } int queryCount(const string& s) { int p = 0; for (char c : s) { int id = c - 'a'; if (trie[p][id] == 0) return 0; p = trie[p][id]; } return cnt[p]; }

trie[p][id]存储的是子节点在数组中的下标，0表示不存在该子节点。根节点使用下标0，每次新建节点就让tot+1。这个“用数组下标代替指针”的思路，其实是图论存图邻接表思想的简化版。

二维数组最大的坑是内存估算。如果你无脑开trie[1000000][26]，一个int占4字节，26个int就是104字节，乘100万就是104MB，容易爆内存。实际开法要看总字符数：假设你有10^5条字符串，每条长度不超过10，那么节点总数最多约10^6，开trie[1000005][26]是10.4MB，完全没问题。如果总字符数逼近10^6，就要考虑用vector<array<int, 26>>边插入边扩容，或者改用孩子兄弟表示法。

5.3 意外收获：Trie还能做最大异或对

很多人的印象里Trie只能处理字符串。实际上，Trie树的本质是“按位分叉的树”，而整数也可以按二进制位分叉。这就引出了一个很惊艳的应用：给n个数，求两个数异或起来的最大值。

思路是把每个数转换成31位二进制，从高位到低位插入01字典树。查询一个数x时，贪心地在每层找与x当前位相反的节点：如果存在就走过去，因为二进制高位不同带来的异或贡献更大；否则只能走相同位的节点。

const int MAX_NODE = 1000000; int trie[MAX_NODE][2]; int tot = 0; void insert(int x) { int p = 0; for (int i = 30; i >= 0; i--) { int bit = (x >> i) & 1; if (trie[p][bit] == 0) trie[p][bit] = ++tot; p = trie[p][bit]; } } int queryMaxXor(int x) { int p = 0, ans = 0; for (int i = 30; i >= 0; i--) { int bit = (x >> i) & 1; if (trie[p][bit ^ 1]) { ans |= (1 << i); p = trie[p][bit ^ 1]; } else { p = trie[p][bit]; } } return ans; }

这题的复杂度是O(31n)，常数稳定，比朴素的O(n^2)不知道高到哪里去了。我第一次做这道题的时候，确实有“数据结构是相通的”这种感觉：同一套树的框架，一套处理字符，一套处理比特，思维模型完全一样。

Trie树相关的高频题还有单词搜索、单词替换、敏感词过滤、自动补全前缀统计等。它并不算难写，但调试时比较容易踩的坑是“查询时忘记判空”，这会导致程序读到一个节点为空的下标，进而访问越界数组。每次用if (!trie[p][id]) return ...这样的判空写全，问题就少一半。

最后再分享一个我自己刷题的习惯：这五类结构不要分开学，要放在一起对比着练。单调栈和单调队列是一对，都在处理“维护候选集合”的问题；并查集是另一根轴，处理的是关系型数据；字符串哈希和Trie树则是处理字符串的两种思路，一个用数字编码，一个用树形结构。每次刷完一类题，试着把下一类跟上，你会发现它们之间有一根很清晰的线连在一起。遇到题目先想“数据范围是多少、查询长什么样、更新频率高不高”，这三个问题答完了，用什么结构基本就出来了。