企业官网建设流程全解析

TYUT-A专题题解（二）来了。上次那篇我把专题的前半部分拆成了暴力枚举和排序技巧，靠那套思路硬啃下来三分之一；这一篇我要聊的是题目单里真正卡住我的那批——单调栈、滑动窗口、并查集。说实话，这套专题第二弹比第一篇有意思得多，它不再考“你知不知道这个函数”，而是考“你相不相信数据结构的抽象能力”。三小时卡在一道中等题上的经历让我明白，这类题的难点绝不在写代码，而在把题目里的约束关系翻译成数据结构语言。这篇题解会把三块内容的原理、模板、典型题和踩坑点一次讲透，适合刚刷完基础线性表、准备进阶的选手。

1. 第二套题的三根柱子：单调栈、滑动窗口、并查集

拿到这个专题的题目单之后，我先做了个分类统计，想看看所谓的“进阶”到底进阶在哪里。整套题大约十二道，难度梯度拉得很开，从十五分钟能秒的水题到需要离线处理的压轴题都有。分类下来其实就三块：单调栈相关四道，滑动窗口相关四道，并查集相关三道，剩下一道是个综合题，把三者揉进了同一个场景。这个分布本身就说明了一个问题——命题人想考察的并不是某个具体算法，而是“扫描历史信息”这个能力。

什么叫“扫描历史信息”？你可以把算法题理解成你在一条街上挨家挨户检查门牌号，每走到一个新位置，你只能知道当前这个位置的信息，历史位置的信息要么你记住，要么你丢掉。单调栈、滑动窗口、并查集，本质上都是问你：什么时候该记，什么时候该丢，以及用什么姿势记才不会乱。

三块内容的难度也不一样，我自己的主观感受如下：

从表格能看出来，这套专题设计的逻辑很清晰：先用单调栈让你体会“用单调性压缩无用信息”，再用滑动窗口让你理解“候选集合的动态维护”，最后用并查集把思维带到“离线处理和倒序思维”。如果你正在刷一套类似的题目不知道怎么规划，我建议你也先按算法类型做一次分类，不要按题目序号硬刷，分类之后你才能看出每道题在练哪一种思维。

2. 单调栈：最近约束关系的维护器

2.1 单调栈到底在维护什么

很多教程喜欢从“维护一个单调的序列”讲起，但我听了半天只能记住结论，根本不知道什么时候该用。后来我自己把它翻译成了一个问题：当我站在当前位置 i，我能不能快速知道向左看第一个小于（或大于）我的元素在哪里？

这个“第一个”很关键。你可以把它理解成排队买奶茶时，每个人想找前面第一个比自己矮的人；形成队列之后，队伍里那些“又高又排在前面”的人实际上永远不会被后面的人选中，因为一旦有一个更矮但更靠后的人出现，前面那些高个子就失去意义了。单调栈做的就是这个淘汰过程：维护一个栈，栈内元素有序，每当新元素要入栈时，先把栈顶那些“不满足单调性”的元素弹出。

这里的核心思路是：那些被弹出的元素，不是没用，而是它们的历史使命已经完成，它们在当前这个新元素面前已经不可能再成为未来某个位置的答案了。理解了这一层，单调栈就不再是死记硬背的模板，而是一种自发的优化直觉。

2.2 三行模板与两个关键下标

先上一个最常用的模板：找到每个元素左边第一个比它小的位置。栈里存的是下标，不是值，这一点新手极容易踩坑。存值虽然也能比较大小，但你最后拿到的只有“这个值是什么”，拿不到“这个值在哪里”，而绝大多数题目的答案是位置。

vector<int> leftSmaller(vector<int>& nums) { int n = nums.size(); vector<int> res(n, -1); stack<int> stk; // 栈里存下标 for (int i = 0; i < n; i++) { while (!stk.empty() && nums[stk.top()] >= nums[i]) { stk.pop(); // 维护严格递增栈 } if (!stk.empty()) res[i] = stk.top(); stk.push(i); // 当前元素下标入栈 } return res; }

细节我展开讲一下。为什么是>=而不是>？这取决于题目要的是“左边第一个严格小于自己的位置”还是“第一个小于等于自己的位置”。如果题目求的是严格小于，那么遇到相等元素时也应该把栈顶弹掉，因为相等元素对严格小于的语义不构成任何帮助。反过来，如果只是找第一个更小的，那么相等时保留栈顶即可，否则你会把答案算错。

另一个容易出错的点是：栈里存下标之后，每次比较都要写nums[stk.top()]，别图省事写了个stk.top()直接和当前值比较，那比较的是下标不是值。这个错属于那种一眼看不出、对拍半天才发现的问题，编译不会报错，逻辑也能跑，就是答案全错。

同理，找右边第一个比自己小的位置，可以倒着遍历，代码几乎对称。我习惯把这两个数组一次性算出来，很多题都需要两边的约束位置一起用。

2.3 从模板到题目：两道上手最快的应用题

典型题一：直方图最大矩形面积。这道题的经典解法是：对每一根柱子，找到它左边第一根比自己矮的柱子和右边第一根比自己矮的柱子，那么这根柱子能扩展出的最大宽度就是两个位置之间的那段。为什么？因为矩形高度由当前柱子决定，左右遇到的第一个比自己矮的柱子就是边界，再往外扩展矩形高度就被压低了。用单调栈分别算左右边界，再扫一遍求最大面积，复杂度 O(n)。

典型题二：所有子数组最小值之和。这道题比上一道要多绕一层。它的核心观察是：如果一个元素是某个子数组的最小值，那么这个子数组不能跨越任何比它小的元素。于是我们又可以借助单调栈找到每个元素左右最近的更小值位置，然后以该元素为最小值的子数组数量就是(i - left) * (right - i)。这个两个括号的乘法我理解了很久才形成肌肉记忆：左边可选起点个数乘以右边可选终点个数，注意都是开区间位置差，不是闭区间。

这两道题的代码骨架一模一样，差别只在最后的统计方式。刷完这两道之后，你对单调栈的理解会从“会写模板”升级到“知道什么时候该用”。

3. 滑动窗口：候选人集合的实时淘汰

3.1 为什么非要用双端队列

滑动窗口最朴素的做法就是每次移动一格窗口，然后扫一遍窗口内找最大值，复杂度 O(nk)，数据一大就歇菜。所以我们要寻求一种增量维护的思路——窗口每次右移一格，只多一个新元素，只少一个旧元素，能不能在 O(1) 时间内拿到新的最大值？

答案是双端队列。但更准确地说，我们需要维护的是一个“候选最大值集合”。窗口里的数字很多，但真正有可能成为最大值的只有那些“新来的且更大的元素”。设想窗口从左往右滑，新加入的元素如果比队尾元素大，那么队列尾部的那些更小元素就再也不可能成为最大值了——因为它们不仅更小，还会更早离开窗口。这个“越老越弱”的双重淘汰，就是滑动窗口能 O(1) 取最大值的本质。

双端队列并不神秘，它就是允许两边同时进出的队列。左边主要用来淘汰那些已经滑出窗口的旧下标，右边用来淘汰那些被新元素压制的老元素。

3.2 滑动窗口最大值模板与边界修正

直接给代码，语言用 C++，STL 的deque够用：

vector<int> maxSlidingWindow(vector<int>& nums, int k) { int n = nums.size(); vector<int> res; deque<int> q; // 存下标，队首是窗口最大值 for (int i = 0; i < n; i++) { // 1. 淘汰滑出窗口的旧下标 while (!q.empty() && q.front() <= i - k) q.pop_front(); // 2. 新元素入队之前，先淘汰队尾的“弱者” while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back(); // 3. 新下标入队 q.push_back(i); // 4. 窗口完整后，记录答案 if (i >= k - 1) res.push_back(nums[q.front()]); } return res; }

这里有三个细节值得反复强调。

第一，队首淘汰的等号。q.front() <= i - k里的等号一定要考虑清楚。窗口覆盖的下标范围是[i - k + 1, i]，也就是说下标i - k已经不在窗口里了。如果队首恰好等于i - k，必须弹出。漏掉等号会让窗口实际宽度变成 k+1，答案在极端情况下会错。

第二，队尾淘汰的等号取决于题目求最大值还是最小值。求最大值时，新元素发现队尾元素比自己小，那队尾就永久失去竞争资格；如果两者相等，我倾向于也把旧元素弹出，因为旧元素会更早离开窗口，留它在队里毫无意义。求最小值时把不等号反过来就行。

第三，记录答案的时机。i >= k - 1意味着窗口的第一个完整形态已经出现，之后再移动一格就有新的窗口形态。很多新手把i > k - 1当成记录时机，导致少记了一个答案，或者数组越界访问队首。

3.3 双指针思路：把“恰好”转化成“最多”

滑动窗口不止双端队列这一种形态。专题里还有一类题问的是“有多少个子数组满足某个条件”，比如“恰好包含 k 个不同字符”。这种题你要是直接维护“恰好”，往往很难统计，因为窗口缩小的边界怎么定都不对。

通用的技巧是转化：“恰好 k 个” = “最多 k 个” - “最多 k-1 个”。于是问题变成了维护“最多 m 个不同字符”的子数组数量。这个统计就简单多了——用双指针 l 和 r 维护窗口，窗口内不同字符数一旦超过 m，就让 l 右移并更新计数，直到恢复合法。对于每个合法的 r，以 r 结尾的满足条件的子数组个数是r - l + 1，全部累加就是答案。

我第一次看到这个转化时觉得有点绕，但仔细想想就明白了：最多 m 个的限制条件让窗口边界变得“只能由超限触发收缩”，而不需要考虑精确数量下界，边界判断就干净了。这种“差一转化”是滑动窗口进阶题里非常高频的思想，值得专门记在本子上。

4. 并查集：从连通性到离线思维

4.1 路径压缩背后到底压缩了什么

并查集应该是中学到大学阶段所有人都会写的第一个树状数据结构。它最核心的操作只有两个：查找某个元素所属集合的代表元、合并两个集合。朴素实现很简单，但一旦数据规模上去，不加优化的并查集会退化成一条链。

路径压缩的原理特别符合直觉：既然我为了找到根节点爬了一大段路，那干脆把路上遇到的所有节点直接挂到根节点下面。这样下次再查它们的时候，一步就到根。这个操作在摊还意义下近乎 O(1)，而且完全不需要额外空间。

但路径压缩不是万能的。它处理的是查询，没法处理“两个节点之间距离信息”的丢失——如果你只把节点指向根，原本父子节点之间的相对关系就被抹掉了。这时候就需要带权并查集。

4.2 按秩合并与带权维护

按秩合并的思路是：把小的树合并到大的树上，避免树长歪。秩可以理解为树的近似高度，合并时让秩小的根指向秩大的根，这样树的深度增长缓慢。路径压缩加按秩合并，并查集的单次操作均摊下来是反阿克曼函数级别，说得通俗点，就是“你可以当它是 O(1)”。

带权并查集我是在这类专题里第一次遇到的，它解决的问题是：集合元素之间存在某种差值或相对关系，合并时不仅要把树连起来，还要把这种相对关系编码进边的权值。举个例子，题目如果告诉你三个人的体重关系：A 比 B 轻 2 公斤，B 比 C 轻 3 公斤，让你求 A 和 C 的差值，那就把每个节点到父节点的“距离”存在权重数组里，查找时进行路径压缩的同时累加边权，合并时根据两个根之间的差异推算出新的边权。

初始化时weight数组全部为 0，代表每个元素到自己的距离是 0。查找时递归找根，递归返回前更新当前节点的父节点为根，同时weight[x] += weight[parent[x]]。合并时如果根不同，就要根据已知关系解一个一元方程算出新边的权值。这一块不熟的话建议先在纸上画几组小数据算一遍，因为光看代码很难理解权重为什么要那样加减，画完图就通了。

4.3 离线倒序加边：删边问题的标准解法

并查集最擅长的是加边，不擅长删边。如果题目问你“删除一条边之后，图还连不连通”，你要是顺着时间线做，并查集就得支持删除，比较复杂。专题里压轴题的核心思路就是离线倒序：先把所有操作读进来，模拟到最后状态的连通关系，然后倒着执行操作，把“删除”变成“加边”。

举个例子，有一张图，初始所有点都孤立，给你若干条加边操作的倒序，你发现倒过来看全是加边，正好匹配并查集的天赋。所以这类题的套路都是三步走：先处理完所有操作后的最终状态，再倒序遍历操作，遇到删除就变成加边并执行 union，把每次连通块的变化记录下来，最后正序输出答案。

这个思想我第一次接触时觉得有点反直觉，但后来在好几道离线数据结构题里都能看到它的影子。它给我的启示是：算法的选择不取决于题目表面问什么，而取决于你的数据流方向是什么。顺着不行就逆着来，数据结构会给你开门。

5. 刷题避坑清单与调试策略

5.1 各题型的常见错误盘点

这一部分是我刷完整套题之后总结的错误清单，每一个都是我或者同学真实踩过的坑，拿出来共享。

这张表我建议你收藏一下，刷之前看一遍能省掉不少 debug 时间。特别提一下单调栈那个“栈里存什么”的问题，看起来是常识，但我在超过三道题里见过有人踩，主要因为写代码时觉得“存值也没差别”，等统计步骤需要坐标时才发现自己手里只有一堆数值，还得重新建立映射关系，白白浪费大量时间。

5.2 我常用的三种调试方法

第一个方法是暴力对拍。对拍不是高端技能，它就是生成小数据，用最朴素的办法算一个正确答案，再跟你的优化算法输出比对。比如单调栈的题目，暴力就是 O(n²) 直接扫每个位置找左右第一个更小的元素，数据规模取 n=10 以内的随机数组。两者输出不同就打印具体数据，不断缩样例。

第二个方法是打印数据结构状态。滑动窗口调试时，我经常在循环里打印当前队列存的下标、队首值、窗口范围，看它每一步是不是按预期淘汰。很多时候你以为队列里存的是窗口最大值候选，打印出来才发现队首早就不是最大值下标了。

第三个方法是构造极简样例。不要用大随机数据开始调，用[1,2,3,4,5]、[5,4,3,2,1]、[2,2,2,2]这种带明显单调性或者全部相等的数组，能最快暴露等于号和边界条件的问题。等极端小样例全过，再上随机对拍就放心了。

这套流程对专题里所有题目都适用。实话说，我在整个专题里写的调试代码量比题解代码量还多，但那部分工作量完全不亏，因为没有对拍，很多隐蔽的错误根本不会浮出水面。

6. 一套可以直接抄的两周训练节奏

最后给一套训练安排，适合每天能抽出两小时左右刷题的人。这套节奏是我根据自己的实践调整过的，第一轮刷到三分之一时觉得进度偏慢，后来压缩了重复题的量才在计划时间内刷完。

第一周主要打基础。前三天主攻单调栈，每天一道新题加一道模板复写；重点是把“找最近更小/更大元素”这件事练出肌肉记忆。第四到第五天转滑动窗口，先刷一道最大/最小值窗口，再刷一道“恰好/最多”转化题，体会双指针的差一思想。第六天松一点，只做一道带权并查集，配合画图理解权重更新。第七天把上一周所有模板题重新默写一遍，允许看着目录回忆，不能看代码。

第二周进入强化和综合。前两天天每天刷两道旧题的新变体，比如把求最大矩形改成求最大子矩阵。第三天到第四天做离线倒序的并查集题，刻意练习“先正序处理再逆序回答”的套路。第五天做专题压轴综合题，允许查资料，但一定要独立跑通。第六天整理一篇自己的错题笔记，像我前面那种表格就很好。第七天找一套新题做限时训练，按考试节奏走一遍，看自己能不能在两小时内做完四道。

这个节奏比较紧凑，如果时间不足可以把第二周拉长到第三周，但核心原则是：不要让任何一个模块的题量少于三道，也不要在一个模块里无限刷题，广度比深度更重要。专题刷到后面你会发现，不同模块的思维方式是会交叉影响的，带权并查集里的边权更新思路有时能帮你想通滑动窗口里的计数问题，这种事只靠刷单一面是做不出来的。

其实把这个专题刷完之后再回头看，最有价值的反而不是这三类数据结构本身，而是那一整套“如何把动态过程抽象成数据结构的扫描与淘汰”的思维模型。做题时每到一个位置，我都会下意识问自己：哪些历史信息必须保留，哪些可以丢弃，怎么丢最快。这套问法在之后的各类题目里都派上了用场。如果你也正在刷类似的进阶专题，耐住性子把每一道题背后的淘汰逻辑想清楚，比赶进度多刷十道题更有意义。