企业官网建设流程全解析

单调栈、单调队列、并查集、字符串哈希、Trie树，这五个名字放在一起的时候，大多数第一次接触算法的朋友都会有点懵——每个字都认识，放一起就不知道是干嘛的了。

这篇习题集锦我整理了半个月，把五类数据结构里最典型、最常考、也最容易踩坑的题目放在一起做对比拆解。目的很直接：让你看完之后，能分得清什么时候该用单调栈、什么时候该用单调队列，能说明白并查集到底"并"的是什么，能理解字符串哈希为什么能O(1)比较两个字符串，也能自己手写一棵Trie树去解决前缀匹配问题。

适合谁看？正在刷LeetCode或洛谷、准备校招面试、搞算法竞赛入门的人，都适合。我会把每个知识点的原理、模板、习题思路、易错点全部串起来讲，配合可直接跑的代码和踩坑记录，争取让你看完能直接"抄作业"式地把这些代码用起来。

1. 整体思路：为什么这五个结构经常被放在一起刷

1.1 五个结构的共同本质：利用"顺序/集合/前缀"做优化

先抛开具体的代码不谈，这五类结构其实都指向同一个核心问题：如何把暴力解法的时间复杂度降下来。

暴力解法在算法题里通常意味着两层甚至三层循环，数据量一上来就超时。而单调栈、单调队列是将"无序的遍历"变成"有秩序的处理"——用栈或队列维护一个单调的序列，把原本需要反复比较的过程压缩到每个元素只进出一次，于是O(n²)级别的问题降到了O(n)。

并查集则解决的是"动态连通性"问题。它不关心图怎么遍历，只关心两个节点现在是否在同一个集合里、能不能快速合并两个集合。这种"合并查询一体化"的思路，在Kruskal最小生成树、判断冗余连接、求连通分量数量等场景里效率极高，接近O(1)。

字符串哈希和Trie树则都针对"字符串比较"这个高频操作。字符串哈希把O(L)的逐字符比较变成O(1)的整数比较；Trie树把前缀匹配变成沿树向下走的O(L)查找。两者路线不同——哈希是"压缩表示"，Trie是"展开存储"——但目标一样：让字符串操作不再成为瓶颈。

1.2 刷题组合策略：先模板、再变形、后综合

我刷这五类题的经验是，不要上来就做难题。必须先掌握标准模板，再用模板去套变形题，最后才是综合题。比如单调栈的模板题是"每日温度"和"下一个更大元素"，变形题是"接雨水"和"柱状图中最大的矩形"，综合题则可能把单调栈和分治、贪心结合。

并查集也是，先写裸的模板（find + union），再写带权并查集（如食物链问题），最后再去碰那些"看似和图论有关但其实是并查集"的题。说实话，很多并查集的题目包装得很好，题干讲的是网格、是好友关系、是冗余连接，一眼看过去根本不像并查集，但拆开之后就是并查集的裸壳。

一个很实用的建议：把这五个结构各自整理成一个"模板文件"，每次做题前先把模板默写一遍。熟练到形成肌肉记忆，做题速度会明显提升。

2. 单调栈：下一个更大元素与区间最值问题

2.1 单调栈的核心原理与生活化类比

单调栈，维护的是一个栈内元素单调递增或单调递减的栈。它的灵魂在于：当新元素入栈时，弹出那些"破坏单调性"的旧元素，而每次弹出时，往往就意味着找到了旧元素的答案。

我举个很生活的例子。想象你们班排队体检，身高从矮到高排成一列。你现在想看每个同学右边第一个比他高的人是谁。最简单的是暴力——每个人往右看，找第一个更高的，复杂度O(n²)。而单调栈的思路是：你从左往右扫描，维持一个从栈底到栈顶递减的"等待者"队列。每当一个新同学过来，如果比栈顶同学高，那么栈顶同学的"右边第一个更高的人"就是新同学，栈顶出栈、答案记录。然后继续比较，直到栈为空或栈顶更高，新同学入栈。

这个过程每个同学只进栈一次、出栈一次，所以总体O(n)。这就是单调栈最核心的应用——解决"下一个更大/更小元素"问题。

2.2 单调栈模板代码（Java/C++双版本）

先看C++版本的标准模板，找每个元素右边第一个比它大的元素（没有则为-1）：

vector<int> nextGreaterElement(vector<int>& nums) { int n = nums.size(); vector<int> res(n, -1); stack<int> st; // 栈里存下标 for (int i = 0; i < n; i++) { // 当前元素比栈顶下标对应的元素大，说明栈顶的答案就是当前元素 while (!st.empty() && nums[i] > nums[st.top()]) { res[st.top()] = nums[i]; st.pop(); } st.push(i); } return res; }

Java版本几乎一样，只是换了语法结构：

public int[] nextGreaterElement(int[] nums) { int n = nums.length; int[] res = new int[n]; Arrays.fill(res, -1); Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { res[stack.pop()] = nums[i]; } stack.push(i); } return res; }

关键细节：栈里存的是下标而不是值。这样做的原因是，你不仅需要知道比栈顶大的值是什么，还需要知道位置——比如求两个元素之间的距离时，存的直接就是下标，算距离非常方便。这个细节我刚学的时候没注意，每次想用值时还得在数组里反查，多此一举。

注意：求"下一个更大元素"维护的是单调递减栈（栈底到栈顶递减），求"下一个更小元素"则反过来，维护单调递增栈。这个方向不要记反了，写错了结果全是反的。

2.3 经典习题实战：柱状图中最大的矩形

这道题是单调栈的进阶题（LeetCode 84），也是面试高频题。题意很简单：给定一个柱状图，每个柱子的宽度为1，求这个柱状图中能勾勒出的矩形的最大面积。

暴力思路是枚举左右边界，然后找区间内最小的高度乘宽度，复杂度O(n³)。优化一步的话，固定一个柱子作为矩形高度，往两边扩展到第一个比它矮的柱子为止，这是O(n²)。单调栈则可以做到O(n)：

核心思路：遍历每个柱子时，用单调栈维护一个递增序列。当遇到比栈顶矮的柱子时，说明以栈顶柱子高度为矩形的边界已经确定，弹出并计算面积。

int largestRectangleArea(vector<int>& heights) { // 在原数组前后各加一个高度为0的柱子，避免遗漏边界处理 heights.push_back(0); heights.insert(heights.begin(), 0); int n = heights.size(); stack<int> st; int maxArea = 0; for (int i = 0; i < n; i++) { while (!st.empty() && heights[i] < heights[st.top()]) { int h = heights[st.top()]; st.pop(); // 当前栈顶位置是左边第一个比h矮的柱子，i是右边第一个比h矮的柱子 int width = i - st.top() - 1; maxArea = max(maxArea, h * width); } st.push(i); } return maxArea; }

我一开始不太理解为啥要前后都加0，后来想明白了：不加右边那个0，最后一个柱子出栈时没有触发条件，面积就漏算了；不加左边那个0，弹出所有栈内元素后st.top()会越界，宽度也没法算。加0在这题里不是可有可无的操作，而是必要哨兵。

画图理解是最重要的。建议你在纸上画一个[2,1,5,6,2,3]的例子，一步一步模拟栈的变化。我第一次刷这道题时就是靠手工模拟的，画了三遍才彻底理解"弹出一个柱子时，新的栈顶刚好就是它左边第一家比它矮的柱子"这个结论。

2.4 单调栈易错点与调试心得

单调栈最大的坑，说来说去其实就三个：

第一个坑是维护方向搞反。求更大元素用递减栈，求更小元素用递增栈。建议做每一道题之前先花十秒钟想清楚："我要找的是更大还是更小？"然后再决定栈的小大方向。

第二个坑是相等元素的处理。有些题明确要求"第一个大于"或"第一个大于等于"，这两个条件对应到栈里的维护方式是不同的。找右边第一个大于的时候，相等的元素不应该被弹出（因为要严格大于）；找第一个大于等于时，相等的元素要被弹出。这个细节经常导致边界用例出错，而且错误结果往往只差一两个位置，非常隐蔽。

第三个坑是边界处理。有些题需要在数组末尾加哨兵，有些题需要同时处理栈中剩余元素。建议做题时养成习惯：循环结束后，检查栈是否为空，如果不为空，需要统一处理栈内剩余元素（通常赋值为-1、0或计算剩余面积）。

调试时推荐一个小技巧：把数组长度限制到5以内，手写一个打印函数，把每一轮循环后栈的内容打出来。查看栈里的元素是递增还是递减的，再对照期望结果，很快就能定位到是方向搞错了还是相等元素的逻辑写错了。

3. 单调队列：滑动窗口最值问题与优化DP的利器

3.1 单调队列与单调栈的本质区别

很多初学者分不清单调栈和单调队列，其实记住一句话就够了：单调栈解决的是"区间内寻找第一个更大/更小"的问题，单调队列解决的是"滑动窗口内寻找最值"的问题。

从数据结构上看，单调队列通常用双端队列（deque）实现，因为我们需要从队尾入队、从队头出队，同时可能要删除队尾元素来维持单调性。它同时支持队头和队尾的增删操作，这是和普通队列最大的不同。

单调队列最经典的场景就是"滑动窗口最大值"（LeetCode 239）。给你一个数组和一个大小为k的滑动窗口，窗口每次向右移动一格，求每个窗口中的最大值。暴力解法是每移动一次就遍历窗口内所有元素，复杂度O(nk)。而单调队列能做到O(n)：

核心思想：队列中始终保持从队头到队尾递减的顺序。新元素入队时，把队尾所有比它小的元素全部弹出，因为它们永远不可能成为窗口最大值了。同时，还要检查队头元素是否已经滑出窗口，如果是则弹出。

3.2 滑动窗口最大值模板与代码实现

vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; // 存下标，保持递减 vector<int> res; for (int i = 0; i < nums.size(); i++) { // 1. 删除队头已经滑出窗口的元素 if (!dq.empty() && dq.front() <= i - k) dq.pop_front(); // 2. 维持单调递减：把队尾所有小于等于当前元素的弹出 while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back(); // 3. 当前元素入队 dq.push_back(i); // 4. 窗口满足长度k之后，队头就是最大值 if (i >= k - 1) res.push_back(nums[dq.front()]); } return res; }

头一次看这段代码可能会懵：为什么要把小于等于当前元素的都弹出？不会丢掉可能的解吗？

不会。因为窗口是向右移动的，当前元素i一定比那些被弹出去的元素更晚离开窗口。如果新元素更大，那在它离开窗口之前，旧元素永远不可能成为窗口最大值，所以保留旧元素没有意义。"比你小还比你走得早"，那这个旧元素自然是"永无出头之日"了。

Java版本同样：

public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] res = new int[n - k + 1]; Deque<Integer> dq = new ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst(); while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast(); dq.offerLast(i); if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()]; } return res; }

注意：判断队头过期用的是dq.front() <= i - k，是小于等于而不是小于。当i等于k时，窗口范围是[0, k-1]，下标为0的元素恰好是窗口左边界，此时它还在窗口内，不需要移除。写成<就会提前删除元素导致错误。

3.3 进阶玩法：单调队列优化DP

如果你刷题刷到动态规划的阶段，你会发现单调队列还有个大用场：优化DP状态转移。

最典型的是"最大子段和"的变种，比如"长度不超过k的最大子段和"、"有限制的连续子数组最大和"。这类题的朴素DP状态转移往往是dp[i] = max(dp[i-1], sum[i] - min{sum[j]})，其中j的取值范围是一个滑动窗口，这时候用单调队列维护这个区间最小值，就能把转移的复杂度从O(k)降到O(1)。

具体来说，一般套路是这样的：先求前缀和数组pre，然后dp[i]代表以第i个元素结尾的最大字段和，转移时我们需要在[i-k, i-1]这个区间内找到一个最小的pre[j]，让pre[i] - pre[j]最大。这个"在滑动窗口内找最小值"的操作，就是单调队列的活。

这类题的核心线索是：只要状态转移方程里出现了"在固定长度的区间内取最值"这种结构，就优先往单调队列上想。

我在刷洛谷的P1440（求m区间内的最小值）时就深刻体会了这一点。那道题其实和滑动窗口几乎一模一样，只是改了个包装而已。

3.4 单调队列易错清单

• 队列里存下标是铁律，不要存值。因为你需要判断过期条件front <= i - k，不存下标根本没法判断。
• 入队顺序有讲究：先弹出过期队头，再弹掉队尾较小元素，最后入队。这个顺序千万别乱。如果先入队再删队头，新元素刚入队就被当成过期元素弹出去了，直接出bug。
• 很多题目要求最小值，那就把"维护递减队列"换成"维护递增队列"，其他逻辑一字不变。所以我建议写模板时只写一套（比如最大值的），用的时候想清楚取反方向即可。

4. 并查集：动态连通性的最优解

4.1 并查集在解决什么问题

并查集这个名字很直白："并"就是合并两个集合，"查"就是查找某个元素属于哪个集合，"集"就是集合。它解决的核心问题是：在只知道点和点之间关系的情况下，快速判断两个点是否连通，并快速合并两个连通块。

生活化的例子就是微信好友的"共同群聊"。假设你有一个好友A和好友B，你不知道他们俩是不是在同一个群里。如果每个群都记一遍所有人，那查询会很慢。并查集的做法是：给每个群选一个"群主"，每个成员都指向自己的群主。查A和B在不在一个群，只需要看他们的群主是不是同一个人即可。合并两个群，就把其中一个群的群主改成另一个群的群主。

并查集在竞赛和面试里的出场率极高。LeetCode的"省份数量"、"冗余连接"、"账户合并"，洛谷的"修复公路"、"亲戚"，这些都是并查集的经典表示。图论里的Kruskal最小生成树算法，也正是基于并查集来判断是否形成环的。

4.2 并查集模板：路径压缩与按秩合并

并查集的标准模板用C++实现如下：

class UnionFind { private: vector<int> parent; // parent[i]表示i的父节点 vector<int> rank; // rank[i]表示树的秩（大致高度） public: UnionFind(int n) { parent.resize(n); rank.resize(n, 0); for (int i = 0; i < n; i++) parent[i] = i; // 初始时每个节点自成一派 } int find(int x) { // 路径压缩：直接让x指向根节点 if (parent[x] != x) { parent[x] = find(parent[x]); // 递归寻找祖先，沿途扁平化 } return parent[x]; } void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) return; // 已经在同一个集合里 // 按秩合并：高度小的树接到高度大的树上 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } } bool connected(int x, int y) { return find(x) == find(y); } };

两个核心优化的意义必须理解透。路径压缩是在find的时候顺便把沿途节点的父节点直接改成根节点，这样下次查询就快了。按秩合并是在unite的时候，总是让高度较小的树作为子树接到高度较大的树上，防止树退化成链表。

注意，rank数组这里我称呼为"秩"而不是"高度"。因为经过路径压缩后，树的实际高度会发生变化，"秩"只是高度的一个上界估计。两者同时使用，单次操作的均摊复杂度是O(α(n))，其中α(n)是反阿克曼函数，增长极其缓慢，对实际数据规模来说可以认为是常数级。

提示：只做路径压缩的并查集也能通过绝大多数题目。但遇到特意构造的数据（洛谷的P3367就曾出过卡并查集的极端样例），如果只做路径压缩不做按秩合并，有可能会超时。最稳妥的写法是两个优化都写上。

4.3 带权并查集：食物链问题全解析

如果你刷并查集刷得比较深，一定会碰到带权并查集，最经典的题目就是POJ 1182"食物链"。

这道题的背景是：动物分三类A、B、C，A吃B，B吃C，C吃A。给出一系列"X和Y是同类"或"X吃Y"的陈述，要求判断哪些陈述是假的。

带权并查集的思路是：不仅在并查集中记录元素属于哪个集合，还记录每个节点相对于根节点的"关系"。用0表示与根节点同类、1表示吃根节点、2表示被根节点吃（或者反过来，看你怎么定义）。这个关系存储在一个数组rel[i]中，每次合并和查找时都需要更新关系。

关键难点在find的路径压缩过程中，关系的更新逻辑：

int find(int x) { if (parent[x] == x) return x; int oldRoot = parent[x]; parent[x] = find(parent[x]); rel[x] = (rel[x] + rel[oldRoot]) % 3; // 关系合并公式 return parent[x]; }

如果自己推这个公式，核心是搞清楚"儿子到爷爷的关系 = 儿子到父亲的关系 + 父亲到爷爷的关系（模3）"。每次查询两个元素是否同类或吃与被吃关系，需要检查它们和各自根节点的关系，再通过差值计算互相间的关系。

建议先别急着看题解，自己画一棵小树，手动模拟合并几次，把关系值填出来，感受一下rel数组是如何传递的。我第一次接触这块时直接看题解，完全看不懂，后来拿笔推了半个小时才反应过来。带权并查集几乎不会考裸模板，而是考"你是否理解了关系是如何随路径压缩传递的"。

4.4 并查集的实际应用判断：哪些题该用它

我总结了三个判断标准，命中任意一条就优先考虑并查集：

第一，题面中出现"连通"、"联通"、"合并"、"分组"这类关键词，而且数据规模较大。比如"判断图中两点是否连通"这类问题，BFS/DFS也可以，但并查集代码更短、常数更小。

第二，题目要求动态地在图上加边，同时查询连通性。比如"冗余连接"那道题，给一堆边，找到第一条能让图出现环的边。用并查集逐条加入边，如果发现一条边的两个端点已经在同一个集合里，就说明加这条边会成环，这条边就是答案。这个思路比起每次加边后跑一遍BFS要快得多。

第三，Kruskal最小生成树。把边按权值从小到大排序，按顺序用并查集判断两端点是否在同一集合，如果不在就加入这条边并合并。这个算法是并查集在图论里的标准应用，几乎每个图论课都会讲。

并查集不是万能的。如果题目要求的是"两个点之间的最短距离"或者"路径的具体长什么样"，那并查集帮不上忙，得用最短路径或DFS/BFS。简单说就是：只关心"在不在同一个集合"，用并查集；关心"怎么走、走多远"，别用并查集。

5. 字符串哈希：O(1)比较字符串的隐藏武器

5.1 字符串哈希的基本思想与公式推导

字符串哈希，简单地说，就是把一个字符串映射成一个整数。这个整数可以看作是字符串的"指纹"。

我们通常用多项式哈希：把字符串看作一个base进制的数。比如字符串"abc"，设base=131，则哈希值为a * 131^2 + b * 131 + c（其中每个字符取ASCII码或字母编号）。

为什么要这么做？因为两个字符串的哈希值相等，我们就认为这两个字符串大概率相等。这样原本O(L)的字符串比较，就降到了O(1)的整数比较。

在实际做预处理后，我们可以O(1)地算出任意子串的哈希值。假设我们有一个前缀哈希数组h[i]表示前i个字符的哈希值，那么子串[l, r]的哈希值可以这样算：

hash(l, r) = h[r] - h[l-1] * base^(r-l+1)

这里的base^(r-l+1)需要提前预处理到一个幂次数组里。这个公式的原理是：h[r]包含了前r个字符的信息，h[l-1] * base^(r-l+1)是把前l-1个字符的信息"平移"到和h[r]对齐的位次上，相减之后就只剩下子串[l, r]的信息了。

5.2 模板代码：前缀哈希和任意子串哈希

const int MAXN = 100005; const unsigned long long base = 131; // 自然溢出取模 unsigned long long h[MAXN]; // 前缀哈希 unsigned long long p[MAXN]; // base的幂次 void initHash(string s) { int n = s.size(); p[0] = 1; for (int i = 1; i <= n; i++) { h[i] = h[i-1] * base + (unsigned long long)(s[i-1] - 'a' + 1); // 字符映射到1~26 p[i] = p[i-1] * base; } } unsigned long long getHash(int l, int r) { // 子串下标从1开始（即原始字符串的l-1到r-1） return h[r] - h[l-1] * p[r-l+1]; }

这里用unsigned long long是故意的。C++的无符号整型溢出时会自动对2^64取模，相当于我们免费获得了一个取模操作。这样写虽然省事，但有它的缺陷——冲突概率比双哈希要高，后文会展开。

一个关键点是字符要从1开始映射，不要从0开始。如果字符a映射为0，那"a"的哈希值和"aa"的哈希值可能一样（因为前导零不影响数值，但字符串不同）。把a映射为1就避免了这种情况。

Java实现则受限于没有无符号整型，一般用long配合手动取模，或直接用BigInteger（不推荐，太慢）：

class StringHash { private long[] h, p; private long mod = 1000000007L; private long base = 131L; public StringHash(String s) { int n = s.length(); h = new long[n + 1]; p = new long[n + 1]; p[0] = 1; for (int i = 1; i <= n; i++) { h[i] = (h[i-1] * base + (s.charAt(i-1) - 'a' + 1)) % mod; p[i] = p[i-1] * base % mod; } } public long getHash(int l, int r) { // 返回值是模mod后的哈希值 return ((h[r] - h[l-1] * p[r-l+1] % mod) + mod) % mod; } }

5.3 字符串哈希的经典应用场景

字符串哈希最强的地方在于，当其他算法还在面对"字符串比较"这个复杂操作时，它已经把复杂度变成了O(1)的整数比较。

• 最长回文子串：预处理正序哈希和逆序哈希，枚举每个中点，二分长度，用哈希判断前半段和后半段是否相等。时间复杂度O(n log n)，边界条件处理好之后正确率很高。
• 字符串匹配问题：用哈希算模式串的哈希值，然后O(n)扫描主串的每个长度为m的子串，比较哈希值是否相等。这种方法写起来比KMP简单得多，虽然理论上存在冲突可能，但配合双哈希基本可以忽略。
• 判断重复子串：枚举子串长度，用哈希把所有子串的哈希值存入哈希表（这个"哈希"是另一个概念了，注意区分），遇到重复值就说明有重复子串。这是"最长重复子串"问题的一个便捷解法。

字符串哈希最大的问题就是哈希冲突。在面试或者比赛中，单哈希被卡过的案例不少——特别是当你用自然溢出时，有些出题人专门构造"哈希杀手"数据来卡你。

我的建议是：在一般做题时可以用单哈希快速验证思路，但在正式提交时至少使用双哈希。双哈希就是用两个不同的base和两个不同的模数（比如一个用10^9+7，一个用10^9+9），分别算出两个哈希值，只有当两个哈希值都相等时才认为字符串相等。这可以把冲突概率降到几乎可以忽略的程度。

注意：不要用自然溢出单哈希，也不要拿10^9+7单枪匹马去扛。虽然被卡的概率不高，但一旦被卡，你调试一整天都未必能找出来原因，因为冲突点往往在测试数据的特定字符串上。

6. Trie树：前缀匹配与字典存储的优雅解法

6.1 Trie树的结构设计

Trie树（也叫字典树、前缀树）是一种树形结构，每个节点代表一个字符，从根节点到任意节点的路径拼接起来就是一个字符串的前缀。

以插入"cat"、"car"、"dog"三个单词为例，根节点分出c和d两条分支，c节点分出a分支，a节点分出t和r两个分支——这样"ca"这个前缀就被两个单词"cat"和"car"共享了。这种共享前缀的设计，是Trie处理前缀匹配问题的核心优势。

用数组实现Trie树是最常见的写法，因为指针/对象写法内存开销太大，在算法题里容易超内存：

class Trie { private: int ch[100005][26]; // ch[i][j]表示节点i的j号子节点的编号，0号节点是根 int cnt[100005]; // cnt[i]表示节点i被多少个单词经过（用于统计前缀次数） int sz; // 当前节点总数 public: Trie() { memset(ch, 0, sizeof(ch)); memset(cnt, 0, sizeof(cnt)); sz = 1; // 根节点从1开始编号（0留作空节点） } void insert(string word) { int cur = 1; for (char c : word) { int idx = c - 'a'; if (ch[cur][idx] == 0) { ch[cur][idx] = ++sz; } cur = ch[cur][idx]; cnt[cur]++; } } int queryPrefix(string prefix) { int cur = 1; for (char c : prefix) { int idx = c - 'a'; if (ch[cur][idx] == 0) return 0; cur = ch[cur][idx]; } return cnt[cur]; // 返回该前缀被包含的次数 } };

这里有个容易搞混的细节：ch数组每个元素存的是子节点的编号（int类型），而不是字符本身。字符是通过idx = c - 'a'隐式体现在"哪一列"上的。所以节点并不需要存储字符值，它的字符就是"它作为父节点的哪一列分支"。

6.2 Trie树vs字符串哈希：各自的适用边界

很多人会问：Trie树能做的事，哈希很多也能做，那为什么要学Trie？

因为Trie能维护并扩展信息，而哈希只是快照。哈希只能告诉你"这个字符串是不是存在"或者"两个字符串是否相等"，但Trie可以做到：

• 查询某个前缀的所有字符串有哪些
• 在插入的同时维护每个前缀的出现次数
• 处理"最大异或对"这样的二进制树问题（01Trie）

以LeetCode 208"实现Trie"为例，这个题就是裸的实现题，考的是你能不能把Trie的基本操作写对。而"查询单词是否存在"用哈希表确实也行，但"统计有多少个单词以某个前缀开头"这种前缀统计需求，哈希表就不太好写，Trie则可以顺手在插入时维护一个计数数组就搞定。

int数组实现的Trie在数据量大的时候内存占用较高，每个节点都有26个int的空间，哪怕实际只有两个孩子，数组空间还是提前分配好了。所以在内存比较紧的OJ里，可以考虑用vector<map<char,int>>或unordered_map<int,int>来节省空间，但代价是常数变大。做题时优先用数组版，空间不够再换哈希版。

6.3 01Trie：最大异或对题目的优雅解法

Trie树还有一个经典变种：01Trie，专门用来解决"最大异或值"问题。

LeetCode 421"数组中两个数的最大异或值"是这类的代表。给定一个数组，找到两个数使得它们的异或值最大。

解法思路是：先把所有数字的二进制形式（31位或32位）插入到Trie中，每一位作为一层的分支（0或1）。然后对每个数字，在Trie中贪心地走——每一步尽可能走与当前位相反的位，因为异或中1比0大。如果存在相反的分支就走，不存在则走相同分支，最后得到的路径对应的数字就是和当前数字异或最大的数。

class Trie01 { int ch[3000005][2]; int sz; public: Trie01() { memset(ch, 0, sizeof(ch)); sz = 1; } void insert(int x) { int cur = 1; for (int i = 30; i >= 0; i--) { int b = (x >> i) & 1; if (ch[cur][b] == 0) ch[cur][b] = ++sz; cur = ch[cur][b]; } } int query(int x) { int cur = 1; int res = 0; for (int i = 30; i >= 0; i--) { int b = (x >> i) & 1; int want = b ^ 1; // 期望走相反位 if (ch[cur][want] != 0) { res |= (1 << i); // 异或结果为1 cur = ch[cur][want]; } else { cur = ch[cur][b]; // 只能走相同位 } } return res; } };

一个重要的处理细节：位循环从30开始，而不是31。因为题目给出的数范围是[0, 2^31)，最高有效位是30（对应二进制第30位）。如果你从31位开始处理，那第31位所有数都是0，会白白占据树的深度，却没有提供任何信息。当然，如果题目是计算int全范围（含负数），那就要改成从31位开始了。

01Trie写错最多的地方是数组大小开不够。每个数需要31个节点，如果有n个数，数组至少要开n * 31 + 1。我吃过几次亏，开少了直接越界错误，而且因为数组是int型的，越界不一定马上报错，而是可能改坏别的数组导致诡异的bug。

建议：每次写01Trie前，先算好n * 31 + 5，再开数组。这是习惯问题，但对调试效率影响巨大。

6.4 Trie树与其他结构配合的进阶思路

Trie树虽然基础，但它经常作为"解题的一块积木"和其他算法配合使用。

比如和动态规划结合：有些字符串拆分、单词拼接的题目，先把单词表建一棵Trie树，然后在DP转移时查Trie来验证子串是否是合法单词。这样省去了反复用哈希表查找子串的时间。

再比如和DFS结合：Trie天然是一棵树，所以可以很方便地做DFS遍历，输出所有插入过的单词（按字典序）。这在写词典、自动补全系统时是一个很实用的功能，LeetCode也有类似的题（比如"单词搜索II"）。

一个经常被忽视的细节是：Trie树的结构设计决定了很多操作可以"顺路完成"。比如插入一个单词时，沿途经过的所有节点的计数都加1；查询是否存在某个单词时，如果最后停在某个节点，发现这个节点并没有被标记为"单词结尾"，那就说明只是前缀而不是完整单词。所以严格来说，Trie树还需要一个bool isEnd标记来区分"前缀节点"和"单词结束节点"。我上面的模板用cnt顺带兼顾了这个功能（cnt > 0且该节点被标记为单词即可），但如果你做LeetCode 208那种题，建议还是显式加上isEnd字段更清晰。

7. 五类结构对比总结与刷题路线建议

7.1 一张表看透五个结构的核心区别

我把这五个结构放在一起对比，整理成一张表，方便你复习对照：

做题时最简单的判断方法：如果题目要求维护一个"有顺序敏感的区间最值"，用单调栈或单调队列；如果只关心"集合归属"，用并查集；如果只关心"字符串相不相等"，用哈希；如果关心"前缀关系"，用Trie。大多数题目不会同时涉及四个结构，但一旦出现两两组合的题（比如Trie+DP），你做起来就会很吃力，所以基础模板一定要烂熟。

7.2 从零开始的刷题接替顺序建议

我一直认为，学数据结构不能贪多求快。以下是我自己推荐的刷题顺序，按这个顺序走下来，基础会比较扎实：

1. 单调栈入门期（5天）：先做"每日温度"和"下一个更大元素I"，再做"柱状图中最大的矩形"和"接雨水"。前两个是模板题，后两个是进阶应用。
2. 单调队列入门期（3天）：把"滑动窗口最大值"至少做三遍（一遍默写模板、一遍优化、一遍不看代码写出来），再做两道单调队列优化DP的入门题（如"最大子序和"的变种）。
3. 并查集基础期（5天）：先默写UnionFind模板，然后做"省份数量"和"冗余连接"，再看"连通网络的操作次数"。做完这些后挑战一下带权并查集（食物链），不强求一次做对，但一定要理解。
4. 字符串哈希期（4天）：先写一个字符串哈希类封装好，然后做"最长回文子串"（用哈希二分做）、"重复的DNA序列"。哈希的重点是会用双哈希，并且弄明白模数和base怎么选。
5. Trie树期（5天）：先做LeetCode 208裸题，再做"实现前缀树"的变种（如统计前缀数量），最后挑战"最大异或对"（01Trie）。Trie的数组实现一定要写到条件反射的程度。

这条路线大概需要一个月左右，每天保持2-3小时的投入。我当年就是这么走过来的，做题时的最大感受是：等五种结构的模板都写熟之后，再去看任何一道"中等偏上"的题，脑子里会自然浮现"这不是单调栈吗""这可以用并查集"的判断。这种敏锐度，只能靠做题喂出来。

8. 常见报错与调试技巧速查

8.1 五个结构各自的经典报错场景

最近我把一段时间里在讨论区里看到的高频报错整理了一下，每类结构挑一两个最典型的写在这里，你遇到类似问题可以直接对照排查：

8.2 调试思想：小数据手推永远是最快的

我自己调试这些题目时的习惯是这样的：

无论报错原因看起来多"玄学"，先从缩小数据规模开始。比如写单调队列，就把输入改成[1,3,-1,-3,5,3,6,7]和k=3这种教科书例子；写并查集就只放3个节点手动模拟每一轮合并。大多数逻辑错误，在小数据上跑一遍立刻现原形。

如果小数据也正常，那是边界条件的问题。常见的边界有：数组长度等于1、窗口大小等于整个数组长度、输入字符串全相同、并查集有两个节点同时在合并自己。把这些极端情况都测一遍，能覆盖90%以上的隐藏bug。

提示：如果你在做字符串哈希，发现偶尔一两个用例挂了，先别怀疑哈希冲突。90%的情况是你的边界下标算错了（比如l和r的代表方式有偏差）。用最原始的办法，打印出子串字符串本身和计算得到的哈希值，逐一核对两步过程，通常能找到问题。

9. 备战中实用的做题习惯与心得

写到这里，我已经把五个结构从原理到代码再到易错点都过了一遍。剩下的，就是你自己动手去写了。

我给想认真学好这部分内容的朋友三个建议。

第一个建议是建立一个"结构模板笔记"，每个结构一页纸，包含：模板代码、适用场景判断词、易错点、经典题列表。我自己的做法是写在Markdown里，每次做题前先翻开看两分钟，做完题再把这道题的独特思路补记进去。这个笔记后期会变成你复习最宝贵的资料。

第二个建议是不要只看题解，要亲手画图模拟。尤其是单调栈弹栈过程、并查集的树形结构合并和路径压缩、Trie树的插入路径，这些光在脑子里推很容易出错，在纸上画出来一次，胜过看十遍题解。我早期学这些内容时，纸用掉了几十张，但每一步都画明白了之后，代码反而写得快，因为逻辑已经透彻了。

第三个建议是做题时尝试"一题多解"。比如"最长回文子串"可以用字符串哈希+二分，也可以用Manacher算法；"滑动窗口最大值"可以用单调队列，也可以用堆（但堆的复杂度是O(n log n)）。每当你发现一题可以用两种方法做，去对比两种方法的复杂度和编码难度，这能帮你加深对每种结构特性的理解——知道它的优势是什么、劣势是什么、什么情况下应该放弃它。

这五个结构之所以经常被整理成一份习题集锦，不是因为它们长得像，而是因为它们分别是解决"顺序处理、动态连通、快速比较、前缀匹配"这四类基础问题的标准答案。你把这一套打下来，基础就真正扎实了一大半。以后不管遇到多复杂的题目，拆到最后，大概率都能看到这几个熟悉的身影在底层支撑着。