刷题刷到一定量之后很多人会有一种感觉单看某道题解法大概知道但一到组合题就抓瞎。突然遇到“下一段区间里找最大值”“动态维护一堆点的连通关系”“判断两个子串是否相同”“给一堆单词找公共前缀”这几类问题本质上都逃不开今天要写的五块内容单调栈、单调队列、并查集、字符串哈希、Trie树。这篇文章就是一份可收藏的习题集锦式总结。每一块我都会先讲清楚“它到底在解决什么问题”再给一份可以直接抄的C模板然后配上一到两道有代表性的题目拆解最后把我踩过的坑单独列出来。不管你是在准备校招笔试、打算法竞赛还是单纯想把基础数据结构补扎实按这个顺序刷下来收获会比较直观。结构核心能力一句话场景单调栈快速找每个元素左/右第一个更大或更小的位置柱状图最大矩形、每日温度单调队列维护滑动窗口内的最值滑动窗口最大值、单调队列优化DP并查集动态合并集合、查询两点是否连通连通块、最小生成树、关系归类字符串哈希O(1)判断两个子串是否相等字符串匹配、回文判断、文本查重Trie树按前缀组织字符串支持前缀查询词频统计、自动补全、最大异或对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(vectorint heights) { int n heights.size(); vectorint h(n 2, 0); for (int i 1; i n; i) h[i] heights[i - 1]; vectorint 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已经不在窗口内了。比如 k3i5时窗口是[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-l1] % mod mod) % mod这个公式的直觉是h[r]相当于把s[0..r]编码成一个数字h[l-1] * pow[r-l1]是把s[0..l-1]部分左移到对齐的位置减掉之后剩下的就是s[l..r]对应的编码。base的选择很关键。常用的是131、13331、137这些经验值是从竞赛实践里沉淀出来的不要乱选。base要大于字符集大小否则碰撞概率会显著增加。模数常用1e97或1e99也可以直接用模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每次新建节点就让tot1。这个“用数组下标代替指针”的思路其实是图论存图邻接表思想的简化版。二维数组最大的坑是内存估算。如果你无脑开trie[1000000][26]一个int占4字节26个int就是104字节乘100万就是104MB容易爆内存。实际开法要看总字符数假设你有10^5条字符串每条长度不超过10那么节点总数最多约10^6开trie[1000005][26]是10.4MB完全没问题。如果总字符数逼近10^6就要考虑用vectorarrayint, 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树则是处理字符串的两种思路一个用数字编码一个用树形结构。每次刷完一类题试着把下一类跟上你会发现它们之间有一根很清晰的线连在一起。遇到题目先想“数据范围是多少、查询长什么样、更新频率高不高”这三个问题答完了用什么结构基本就出来了。
