单调栈、单调队列、并查集、字符串哈希、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版本的标准模板找每个元素右边第一个比它大的元素没有则为-1vectorint nextGreaterElement(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint 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); DequeInteger 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(vectorint heights) { // 在原数组前后各加一个高度为0的柱子避免遗漏边界处理 heights.push_back(0); heights.insert(heights.begin(), 0); int n heights.size(); stackint 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 滑动窗口最大值模板与代码实现vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; // 存下标保持递减 vectorint 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]; DequeInteger 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: vectorint parent; // parent[i]表示i的父节点 vectorint 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、CA吃BB吃CC吃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设base131则哈希值为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-l1)这里的base^(r-l1)需要提前预处理到一个幂次数组里。这个公式的原理是h[r]包含了前r个字符的信息h[l-1] * base^(r-l1)是把前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-l1]; }这里用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-l1] % mod) mod) % mod; } }5.3 字符串哈希的经典应用场景字符串哈希最强的地方在于当其他算法还在面对字符串比较这个复杂操作时它已经把复杂度变成了O(1)的整数比较。最长回文子串预处理正序哈希和逆序哈希枚举每个中点二分长度用哈希判断前半段和后半段是否相等。时间复杂度O(n log n)边界条件处理好之后正确率很高。字符串匹配问题用哈希算模式串的哈希值然后O(n)扫描主串的每个长度为m的子串比较哈希值是否相等。这种方法写起来比KMP简单得多虽然理论上存在冲突可能但配合双哈希基本可以忽略。判断重复子串枚举子串长度用哈希把所有子串的哈希值存入哈希表这个哈希是另一个概念了注意区分遇到重复值就说明有重复子串。这是最长重复子串问题的一个便捷解法。字符串哈希最大的问题就是哈希冲突。在面试或者比赛中单哈希被卡过的案例不少——特别是当你用自然溢出时有些出题人专门构造哈希杀手数据来卡你。我的建议是在一般做题时可以用单哈希快速验证思路但在正式提交时至少使用双哈希。双哈希就是用两个不同的base和两个不同的模数比如一个用10^97一个用10^99分别算出两个哈希值只有当两个哈希值都相等时才认为字符串相等。这可以把冲突概率降到几乎可以忽略的程度。注意不要用自然溢出单哈希也不要拿10^97单枪匹马去扛。虽然被卡的概率不高但一旦被卡你调试一整天都未必能找出来原因因为冲突点往往在测试数据的特定字符串上。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里可以考虑用vectormapchar,int或unordered_mapint,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 一张表看透五个结构的核心区别我把这五个结构放在一起对比整理成一张表方便你复习对照结构核心问题时间复杂度经典习题典型信号单调栈寻找某个元素一侧第一个更大/更小元素O(n)每日温度、接雨水、柱状图最大矩形下一个更大/更小单调队列滑动窗口内的最值O(n)滑动窗口最大值、m区间最小值窗口内最值并查集动态连通性、合并与查询均摊O(α(n))省份数量、冗余连接、Kruskal是否连通、合并集合字符串哈希O(1)比较字符串/子串预处理O(n)每次查询O(1)重复子串、回文子串、字符串匹配比较两个子串是否相等Trie树前缀匹配、字典存储、二进制贪心插入/查询O(L)实现Trie、最大异或对、单词搜索前缀、单词集合做题时最简单的判断方法如果题目要求维护一个有顺序敏感的区间最值用单调栈或单调队列如果只关心集合归属用并查集如果只关心字符串相不相等用哈希如果关心前缀关系用Trie。大多数题目不会同时涉及四个结构但一旦出现两两组合的题比如TrieDP你做起来就会很吃力所以基础模板一定要烂熟。7.2 从零开始的刷题接替顺序建议我一直认为学数据结构不能贪多求快。以下是我自己推荐的刷题顺序按这个顺序走下来基础会比较扎实单调栈入门期5天先做每日温度和下一个更大元素I再做柱状图中最大的矩形和接雨水。前两个是模板题后两个是进阶应用。单调队列入门期3天把滑动窗口最大值至少做三遍一遍默写模板、一遍优化、一遍不看代码写出来再做两道单调队列优化DP的入门题如最大子序和的变种。并查集基础期5天先默写UnionFind模板然后做省份数量和冗余连接再看连通网络的操作次数。做完这些后挑战一下带权并查集食物链不强求一次做对但一定要理解。字符串哈希期4天先写一个字符串哈希类封装好然后做最长回文子串用哈希二分做、重复的DNA序列。哈希的重点是会用双哈希并且弄明白模数和base怎么选。Trie树期5天先做LeetCode 208裸题再做实现前缀树的变种如统计前缀数量最后挑战最大异或对01Trie。Trie的数组实现一定要写到条件反射的程度。这条路线大概需要一个月左右每天保持2-3小时的投入。我当年就是这么走过来的做题时的最大感受是等五种结构的模板都写熟之后再去看任何一道中等偏上的题脑子里会自然浮现这不是单调栈吗这可以用并查集的判断。这种敏锐度只能靠做题喂出来。8. 常见报错与调试技巧速查8.1 五个结构各自的经典报错场景最近我把一段时间里在讨论区里看到的高频报错整理了一下每类结构挑一两个最典型的写在这里你遇到类似问题可以直接对照排查结构典型报错/错误结果原因分析排查思路单调栈答案数组元素位置错乱栈内存的是值而非下标导致弹栈后无法定位答案位置确认栈内存下标用nums[st.top()]取值单调队列结果整体右偏或左偏过期判断的边界条件写错用了而不是手推小数据k3的滑动过程逐一核对并查集find进入死循环递归find的终止条件写错或路径压缩写成了parent[x] find(parent[parent[x]])检查parent[x] x的终止判断路径压缩只写一行parent[x] find(parent[x])字符串哈希两个子串哈希相等但实际不等模数太小导致冲突或字符从0开始映射换大质数模数改用双哈希字符从1开始映射Trie树运行时报数组越界数组大小不足n*节点深度或节点编号从0开始导致根节点与空节点冲突数组开到n * maxLen 5根节点从1开始编号8.2 调试思想小数据手推永远是最快的我自己调试这些题目时的习惯是这样的无论报错原因看起来多玄学先从缩小数据规模开始。比如写单调队列就把输入改成[1,3,-1,-3,5,3,6,7]和k3这种教科书例子写并查集就只放3个节点手动模拟每一轮合并。大多数逻辑错误在小数据上跑一遍立刻现原形。如果小数据也正常那是边界条件的问题。常见的边界有数组长度等于1、窗口大小等于整个数组长度、输入字符串全相同、并查集有两个节点同时在合并自己。把这些极端情况都测一遍能覆盖90%以上的隐藏bug。提示如果你在做字符串哈希发现偶尔一两个用例挂了先别怀疑哈希冲突。90%的情况是你的边界下标算错了比如l和r的代表方式有偏差。用最原始的办法打印出子串字符串本身和计算得到的哈希值逐一核对两步过程通常能找到问题。9. 备战中实用的做题习惯与心得写到这里我已经把五个结构从原理到代码再到易错点都过了一遍。剩下的就是你自己动手去写了。我给想认真学好这部分内容的朋友三个建议。第一个建议是建立一个结构模板笔记每个结构一页纸包含模板代码、适用场景判断词、易错点、经典题列表。我自己的做法是写在Markdown里每次做题前先翻开看两分钟做完题再把这道题的独特思路补记进去。这个笔记后期会变成你复习最宝贵的资料。第二个建议是不要只看题解要亲手画图模拟。尤其是单调栈弹栈过程、并查集的树形结构合并和路径压缩、Trie树的插入路径这些光在脑子里推很容易出错在纸上画出来一次胜过看十遍题解。我早期学这些内容时纸用掉了几十张但每一步都画明白了之后代码反而写得快因为逻辑已经透彻了。第三个建议是做题时尝试一题多解。比如最长回文子串可以用字符串哈希二分也可以用Manacher算法滑动窗口最大值可以用单调队列也可以用堆但堆的复杂度是O(n log n)。每当你发现一题可以用两种方法做去对比两种方法的复杂度和编码难度这能帮你加深对每种结构特性的理解——知道它的优势是什么、劣势是什么、什么情况下应该放弃它。这五个结构之所以经常被整理成一份习题集锦不是因为它们长得像而是因为它们分别是解决顺序处理、动态连通、快速比较、前缀匹配这四类基础问题的标准答案。你把这一套打下来基础就真正扎实了一大半。以后不管遇到多复杂的题目拆到最后大概率都能看到这几个熟悉的身影在底层支撑着。
