提到“离散化”和“区间合并”很多刚入门的朋友第一反应是把浮点数转成整数这理解差了十万八千里。算法题里说的离散化准确讲叫“坐标离散化”或“值域压缩”核心思想是把一组零散的大整数坐标映射成一个从0开始的连续整型下标。再配上区间合并两个算法组合起来能解决一类特别常见的问题给你一堆区间或矩形坐标范围大得离谱但数量很少问你覆盖情况如何。这篇文章会用矩形覆盖面积的经典题把两个算法的原理、模板代码、易错点从头到尾拆一遍。适合困惑于这些题“到底为什么这样做”的人看也适合面试前突击区间处理专题的读者。不管你是刷竞赛题还是找研发岗这两个词放在一起出现时基本就是暗示别按原始坐标硬来先压一压。1. 离散化把上亿格子的数轴压缩成一个数组1.1 什么时候需要离散化先看一个最典型的场景。数轴上有从1到10^9的一堆格子现在给你N个操作每个操作给一个区间[L, R]要求把区间内所有格子染色最后统计被染色的格子数量。如果直接开一个长度为10^9的数组内存直接爆掉。就算用map按需记录每次操作都要遍历一遍区间内的每个点复杂度也高得离谱。但仔细想想10^9个位置里真正有用的其实只有区间的端点。比如操作区间是[1, 1000000000]、[100000000, 200000000]那整个数轴上真正重要的坐标就只有1、100000000、200000000、1000000000这4个。中间那些格子虽然在操作范围里但并不会影响我们的统计逻辑——它们之间要么全被覆盖要么全没被覆盖状态是一致的。这就是离散化的适用条件数据的“取值空间”远大于“实际出现的不同数值个数”。在算法题里典型的信号是题目给出的坐标值动不动到10^9甚至更大而操作数N通常只有10^5量级。这时候把坐标按大小排个序、编个号就能用数组下标的连续区间去代表原始坐标之间的连续范围。1.2 两种常用实现方式离散化主要分两步第一步收集所有可能被访问到的坐标值去重排序第二步把原始值映射成排序后的下标。收集这一步没什么好说的就是把所有操作的端点、查询的坐标一股脑丢进一个数组。映射这一步有两种常见做法第一种是用unordered_map做哈希映射写起来直接查起来平均O(1)。但问题在于哈希表常数大在10^5甚至10^6的规模下并不划算而且如果是预先不知道所有坐标、边读入边查询的场景你还得先扫一遍才能建表。第二种是用vector配合lower_bound做二分映射这是我在竞赛题和面试题里最推荐的写法。先排序去重然后查询时二分找位置复杂度稳定在O(logM)M是去重后坐标个数。代码也就三行vectorint alls; sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); auto get_id [](int x) { return lower_bound(alls.begin(), alls.end(), x) - alls.begin(); };这里的get_id(x)返回的是x在排序去重数组中的下标也就是映射后的新坐标。经过这一映射原始坐标范围从10^9被压缩到最多2N个连续下标之后的算法复杂度就可以安稳地依赖N而不是依赖坐标范围了。1.3 一个必须想清楚的前提离散化只关心“相对大小和相等关系”不关心坐标之间的绝对距离。[1, 2]和[1, 1000000000]离散化后如果只存端点前者是[0, 1]后者是[0, 1]看起来一模一样但实际代表的范围长度完全不同。所以如果题目要求计算长度、面积这类依赖真实距离的指标离散化只能帮你把坐标“编号”真正算长度的时候一定要回到原始坐标用原始坐标差和新编号做对应。这个点特别容易踩坑后面第三部分矩形面积并就是典型例子——所有面积计算用的都是原始坐标的差值离散化只负责划分子问题。2. 区间合并一堂课搞懂重叠区间的清理逻辑2.1 区间合并到底在合并什么给你若干个区间区间之间可能嵌套、可能部分重叠、可能完全不相连。区间合并做的事情就是把有交集包括边界接触的区间合并成一个更大的区间最后输出一组互不相交的区间。举个例子[1, 3]、[2, 6]、[8, 10]、[9, 12]合并之后就是[1, 6]和[8, 12]。[2, 6]和[1, 3]重叠合成[1, 6][9, 12]和[8, 10]重叠合成[8, 12]但[6, 8]之间空了一格所以两组合并结果分道扬镳。核心思路非常单纯先把所有区间按左端点升序排序然后从左到右扫一遍维护当前合并块的左右端点。扫描时只要发现新区间的左端点小于等于当前合并块的右端点说明两者连上了就把右端点更新成两者中最大的那个否则当前合并块已经“定型”把它输出再用新区间开启一个新的合并块。2.2 排序策略的底层逻辑为什么非按左端点排这是理解整个算法的关键。想象你面前有一堆区间。如果按左端点升序排序那么扫到第i个区间时它的左端点一定不小于前面所有区间的左端点。这意味着后面出现的区间只可能“向外延伸”不可能再回头覆盖前面某个区间左侧的部分。在这种情况下你只需要维护一个当前合并块的右端点就能判断新区间是否与当前块重叠——只要新区间的左端点落在了当前块的范围内它顶多让当前块变宽一些绝不会产生“当前块早该关闭但后面又冒出一个能覆盖它左边部分的区间”的问题。如果按右端点排序逻辑就会变得一团糟。因为后面出现的区间左端点可能很小直接覆盖前面已经“定型”的区间合并就得反复横跳写出来的代码复杂且容易错。2.3 合并模板与复杂度标准模板如下这个写法我在简历上直接默写过不下二十遍vectorpairint, int merge(vectorpairint, int segs) { if (segs.empty()) return {}; sort(segs.begin(), segs.end()); vectorpairint, int res; int st segs[0].first, ed segs[0].second; for (int i 1; i (int)segs.size(); i) { if (segs[i].first ed) { ed max(ed, segs[i].second); } else { res.push_back({st, ed}); st segs[i].first; ed segs[i].second; } } res.push_back({st, ed}); return res; }注意最后res.push_back({st, ed})千万别省。循环只负责把“结束的合并块”存起来而遍历结束后肯定还有一个未存储的合并块漏掉它结果就会缺最后一段。整个算法的时间复杂度是排序的O(NlogN)加遍历的O(N)总复杂度O(NlogN)。在竞赛题的数据规模下这个复杂度非常舒适。3. 组合拳实战矩形覆盖面积计算的完整实现3.1 题目为什么会同时用上两个算法矩形的左下角和右上角坐标都给出来N个矩形可能有重叠求它们覆盖的总面积。坐标范围是0到10^9N最多到10^5量级。这就是一个典型的“离散化 区间合并”组合问题。为什么不能直接遍历所有格点因为坐标范围太大。为什么只离散化就能解决还是太大因为矩形面积是二维的单纯把x坐标或y坐标压缩另一个维度依然会大得离谱。正确思路是错位切分先把所有矩形的x坐标收集起来排序去重。每两个相邻x坐标之间夹着一个垂直条带条带的宽度就是两个原始x坐标的差。由于条带两侧正好落在所有矩形的边界上任何一个矩形对某个条带只有两种状态完全包含这个条带矩形横跨L到R或者根本碰不到它。不存在“只盖住条带一半”的模棱两可。所以每个条带内部的任务变成一个一维问题收集所有横跨该条带的矩形把这些矩形的y方向区间拿出来做一遍区间合并合并出覆盖的总长度再乘以条带宽度就是该条带的覆盖面积。把所有条带的面积累加得到总面积。3.2 分步实现先切条带再做一维合并第一步收集所有矩形的x1、x2排序去重得到xs数组。第二步遍历xs的相邻元素对(xs[i], xs[i1])对每个条带扫描所有矩形如果rect.x1 xs[i] xs[i1] rect.x2说明矩形横跨整个条带把它的y区间(rect.y1, rect.y2)收集起来。第三步对这些y区间做区间合并计算覆盖高度然后累加height * (xs[i1] - xs[i])。这里有个关键细节宽度必须用原始坐标的差值而不是离散化后的下标差值。因为离散化丢掉了坐标之间“真实距离”的信息下标间隔1可能代表真实距离1也可能代表100000000必须回到原始坐标取值。3.3 完整代码与手工验证以下是可以直接编译运行的C代码#include bits/stdc.h using namespace std; using ll long long; struct Rect { ll x1, y1, x2, y2; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorRect rects(n); vectorll xs; for (auto r : rects) { cin r.x1 r.y1 r.x2 r.y2; xs.push_back(r.x1); xs.push_back(r.x2); } // 1. x坐标离散化 sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); ll ans 0; // 2. 枚举相邻x坐标构成的条带 for (int i 0; i 1 (int)xs.size(); i) { ll L xs[i], R xs[i 1]; ll width R - L; vectorpairll, ll segs; for (auto r : rects) { if (r.x1 L R r.x2) { segs.push_back({r.y1, r.y2}); } } if (segs.empty()) continue; // 3. 对y区间做合并 sort(segs.begin(), segs.end()); ll st segs[0].first, ed segs[0].second; ll cover_len 0; for (int j 1; j (int)segs.size(); j) { if (segs[j].first ed) { ed max(ed, segs[j].second); } else { cover_len ed - st; st segs[j].first; ed segs[j].second; } } cover_len ed - st; ans cover_len * width; } cout ans endl; return 0; }我拿一个经典样例验证过。三个矩形(0,0)-(2,2)、(1,1)-(3,3)、(2,0)-(4,2)。x坐标收集为0,1,2,3,4分成四个条带。条带[0,1]只有第一个矩形覆盖y区间[0,2]高度2面积2。条带[1,2]有前两个矩形覆盖y区间是[0,2]和[1,3]合并成[0,3]高度3面积3。条带[2,3]有后两个矩形覆盖y区间是[1,3]和[0,2]合并成[0,3]高度3面积3。条带[3,4]只有第三个矩形覆盖y区间[0,2]高度2面积2。总面积10和手工数矩形重叠区域得到的结果完全一致。4. 面试与竞赛中的高频变体和易错点4.1 各种五花八门的考察方式区间合并这题的变体非常多。LeetCode 56题“合并区间”就是裸模板题LeetCode 57题“插入区间”可以先把新区间插入原数组再合并LeetCode 759题“员工空闲时间”本质上是在多条时间轴上找覆盖次数为0的区间做法是把所有区间按左端点排序后合并再检查合并结果之间的空隙。离散化的变体更多。最常见的是“区间加值”给一个很大的数轴做N次区间加法最后查询某个位置的值。做法是收集所有区间的左右端点离散化后对相邻坐标之间的“段”做差分最后用前缀和恢复。还有一类题目把离散化和区间合并藏在更复杂的包装里比如给一堆矩形求周长、求多个区间的交集总长度、求某时间段内空闲区间等等。解题思路都有一个共同模式发现问题本质是“若干区间之间的关系计算”然后套上合并模板。4.2 典型踩坑现场汇总我用一张表把常见错误列清楚。这些坑我都踩过一遍写出来帮你少走弯路错误操作实际后果正确做法区间合并前忘记排序合并结果错乱左右端点乱跳任何合并操作前先按左端点排序用而不是判断重叠相邻区间不合并少算覆盖长度边界接触也算重叠用遍历结束后忘了push最后一个块答案正好少了最后一段区间循环结束后必须push_back({st, ed})用int存储坐标和面积数据一大直接溢出坐标和面积一律用long long离散化后用错映射方式坐标对应下标错误结果完全不可信用lower_bound二分映射确保返回值使用正确矩形条带覆盖判断写成L r.x1 R r.x2这类反向条件条带漏算或重复计算用r.x1 L R r.x2确认矩形完全覆盖条带这里面最隐蔽的是边界符号问题。区间合并如果处理的是“连续长度”两个区间只要端点接触就应该合并因为[1,2]和[2,3]合起来的连续覆盖长度确实是2。但如果题目统计的是“整数点的数量”[1,2]覆盖2个点[2,3]也覆盖2个点合并成[1,3]后是3个点而不是4个点这时合并条件就要用segs[i].first ed 1而不是 ed。具体用什么一定先想清楚题目要的是长度还是点数。4.3 排查问题时的调试技巧区间合并这类题出错时调试手段其实很朴素但不丢人。第一招把每次合并的中间结果用cerr打出来观察st和ed的更新轨迹是否符合预期。第二招自己构造几个极端样例所有区间共享一个端点、一个区间完全包含另一个区间、区间彼此相邻但不重合、只有一个区间。这四种情况基本能把代码run出八成的问题。第三招是最实在的写一个暴力解做对拍。暴力解法就是按坐标范围直接标记数组或直接按面积公式算数据量设小一点随机生成几十组数据把暴力解和优化解的输出逐一比对。一旦对拍出错把出错的随机数据唯一化手工推一遍就能定位。这套调试流程我至今还在用。很多时候不是算法不会是写出来总有那么一两处边界判断的细节不对对拍就是最直接的方式。5. 从坐标离散化到更广的领域5.1 差分数组与离散化的强力配合离散化最常见的搭档其实不是区间合并而是差分数组。看一个场景数轴坐标范围极大但只有N个区间操作每个操作给区间[L, R]加一个值v最后要一次性输出所有端点的值。照搬原始差分思路会死人因为数组根本开不下。做法是先离散化所有端点然后把“相邻离散点之间的整段区域”当作差分数组的元素。原始区间[L, R]映射成离散化下标后在下标区间上做差分。最后前缀和恢复时每段的值就是这一段内所有点的统一值。举个小例子坐标集合是{1, 3, 7, 12}离散化后下标0,1,2,3。对区间[3, 7]加1只需在离散化数组下标1到2之间做差分而不是在3到7的每个点上操作。这样数据规模被压缩到操作端点数量级复杂度立刻降下来。5.2 扫描线算法当离散化遇到更重的数据结构其实矩形面积并还有一种更进阶的解法叫扫描线。做法是把所有矩形的上下边拆成事件按y坐标扫描用线段树维护当前x方向的有效覆盖长度。扫描线算法和上面讲的“条带遍历法”核心一致都是先把一个维度离散化再对另一个维度做区间合并。区别只是扫描线用线段树把区间合并的复杂度降到了每次O(logN)整体复杂度从O(N^2logN)降到O(NlogN)。如果你在面试时写了条带遍历法面试官追问“能不能更快”答案就是扫描线。理解这条递进关系很重要不是两个割裂的算法而是同一个思想在不同数据结构支撑下的两种实现形式。5.3 “离散化”这个词在不同领域含义完全不同最后想提个容易混淆的问题。看到“离散化”三个字时注意它在不同领域的含义差别很大。算法竞赛和面试题里的离散化指的是坐标压缩把一个稀疏取值的大值域映射成紧凑下标。但在控制工程、电力电子领域比如SVPWM算法、多二阶广义积分器的讨论里离散化通常指的是把连续时间的微分方程转换成差分方程把模拟控制器变成数字控制器里的迭代公式。这两个意思差了十万八千里。如果你看到有人聊SVPWM算法时说“离散化”千万别把坐标压缩那套思路套进去。同样一个词两个圈子指代完全不同的操作。知道这个区别能避免不少沟通中的尴尬。我个人在实际操作中的体会是面试中遇到区间类问题看到坐标范围大到没法开数组第一反应就应该是离散化看到“合并区间”“区间覆盖总长”“求覆盖面积”这类字眼第一反应就应该是区间合并。很多时候把这两个词写进思维流程里再难的题也会有方向。最后分享一个练习技巧把那道矩形覆盖面积题反复敲三遍每遍不参考代码敲到能一口气完成为止。等这个熟练了你再看扫描线代码都不会犯怵。这算是踩坑踩出来的心得供每位读者参考。
提到“离散化”和“区间合并”很多刚入门的朋友第一反应是把浮点数转成整数这理解差了十万八千里。算法题里说的离散化准确讲叫“坐标离散化”或“值域压缩”核心思想是把一组零散的大整数坐标映射成一个从0开始的连续整型下标。再配上区间合并两个算法组合起来能解决一类特别常见的问题给你一堆区间或矩形坐标范围大得离谱但数量很少问你覆盖情况如何。这篇文章会用矩形覆盖面积的经典题把两个算法的原理、模板代码、易错点从头到尾拆一遍。适合困惑于这些题“到底为什么这样做”的人看也适合面试前突击区间处理专题的读者。不管你是刷竞赛题还是找研发岗这两个词放在一起出现时基本就是暗示别按原始坐标硬来先压一压。1. 离散化把上亿格子的数轴压缩成一个数组1.1 什么时候需要离散化先看一个最典型的场景。数轴上有从1到10^9的一堆格子现在给你N个操作每个操作给一个区间[L, R]要求把区间内所有格子染色最后统计被染色的格子数量。如果直接开一个长度为10^9的数组内存直接爆掉。就算用map按需记录每次操作都要遍历一遍区间内的每个点复杂度也高得离谱。但仔细想想10^9个位置里真正有用的其实只有区间的端点。比如操作区间是[1, 1000000000]、[100000000, 200000000]那整个数轴上真正重要的坐标就只有1、100000000、200000000、1000000000这4个。中间那些格子虽然在操作范围里但并不会影响我们的统计逻辑——它们之间要么全被覆盖要么全没被覆盖状态是一致的。这就是离散化的适用条件数据的“取值空间”远大于“实际出现的不同数值个数”。在算法题里典型的信号是题目给出的坐标值动不动到10^9甚至更大而操作数N通常只有10^5量级。这时候把坐标按大小排个序、编个号就能用数组下标的连续区间去代表原始坐标之间的连续范围。1.2 两种常用实现方式离散化主要分两步第一步收集所有可能被访问到的坐标值去重排序第二步把原始值映射成排序后的下标。收集这一步没什么好说的就是把所有操作的端点、查询的坐标一股脑丢进一个数组。映射这一步有两种常见做法第一种是用unordered_map做哈希映射写起来直接查起来平均O(1)。但问题在于哈希表常数大在10^5甚至10^6的规模下并不划算而且如果是预先不知道所有坐标、边读入边查询的场景你还得先扫一遍才能建表。第二种是用vector配合lower_bound做二分映射这是我在竞赛题和面试题里最推荐的写法。先排序去重然后查询时二分找位置复杂度稳定在O(logM)M是去重后坐标个数。代码也就三行vectorint alls; sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); auto get_id [](int x) { return lower_bound(alls.begin(), alls.end(), x) - alls.begin(); };这里的get_id(x)返回的是x在排序去重数组中的下标也就是映射后的新坐标。经过这一映射原始坐标范围从10^9被压缩到最多2N个连续下标之后的算法复杂度就可以安稳地依赖N而不是依赖坐标范围了。1.3 一个必须想清楚的前提离散化只关心“相对大小和相等关系”不关心坐标之间的绝对距离。[1, 2]和[1, 1000000000]离散化后如果只存端点前者是[0, 1]后者是[0, 1]看起来一模一样但实际代表的范围长度完全不同。所以如果题目要求计算长度、面积这类依赖真实距离的指标离散化只能帮你把坐标“编号”真正算长度的时候一定要回到原始坐标用原始坐标差和新编号做对应。这个点特别容易踩坑后面第三部分矩形面积并就是典型例子——所有面积计算用的都是原始坐标的差值离散化只负责划分子问题。2. 区间合并一堂课搞懂重叠区间的清理逻辑2.1 区间合并到底在合并什么给你若干个区间区间之间可能嵌套、可能部分重叠、可能完全不相连。区间合并做的事情就是把有交集包括边界接触的区间合并成一个更大的区间最后输出一组互不相交的区间。举个例子[1, 3]、[2, 6]、[8, 10]、[9, 12]合并之后就是[1, 6]和[8, 12]。[2, 6]和[1, 3]重叠合成[1, 6][9, 12]和[8, 10]重叠合成[8, 12]但[6, 8]之间空了一格所以两组合并结果分道扬镳。核心思路非常单纯先把所有区间按左端点升序排序然后从左到右扫一遍维护当前合并块的左右端点。扫描时只要发现新区间的左端点小于等于当前合并块的右端点说明两者连上了就把右端点更新成两者中最大的那个否则当前合并块已经“定型”把它输出再用新区间开启一个新的合并块。2.2 排序策略的底层逻辑为什么非按左端点排这是理解整个算法的关键。想象你面前有一堆区间。如果按左端点升序排序那么扫到第i个区间时它的左端点一定不小于前面所有区间的左端点。这意味着后面出现的区间只可能“向外延伸”不可能再回头覆盖前面某个区间左侧的部分。在这种情况下你只需要维护一个当前合并块的右端点就能判断新区间是否与当前块重叠——只要新区间的左端点落在了当前块的范围内它顶多让当前块变宽一些绝不会产生“当前块早该关闭但后面又冒出一个能覆盖它左边部分的区间”的问题。如果按右端点排序逻辑就会变得一团糟。因为后面出现的区间左端点可能很小直接覆盖前面已经“定型”的区间合并就得反复横跳写出来的代码复杂且容易错。2.3 合并模板与复杂度标准模板如下这个写法我在简历上直接默写过不下二十遍vectorpairint, int merge(vectorpairint, int segs) { if (segs.empty()) return {}; sort(segs.begin(), segs.end()); vectorpairint, int res; int st segs[0].first, ed segs[0].second; for (int i 1; i (int)segs.size(); i) { if (segs[i].first ed) { ed max(ed, segs[i].second); } else { res.push_back({st, ed}); st segs[i].first; ed segs[i].second; } } res.push_back({st, ed}); return res; }注意最后res.push_back({st, ed})千万别省。循环只负责把“结束的合并块”存起来而遍历结束后肯定还有一个未存储的合并块漏掉它结果就会缺最后一段。整个算法的时间复杂度是排序的O(NlogN)加遍历的O(N)总复杂度O(NlogN)。在竞赛题的数据规模下这个复杂度非常舒适。3. 组合拳实战矩形覆盖面积计算的完整实现3.1 题目为什么会同时用上两个算法矩形的左下角和右上角坐标都给出来N个矩形可能有重叠求它们覆盖的总面积。坐标范围是0到10^9N最多到10^5量级。这就是一个典型的“离散化 区间合并”组合问题。为什么不能直接遍历所有格点因为坐标范围太大。为什么只离散化就能解决还是太大因为矩形面积是二维的单纯把x坐标或y坐标压缩另一个维度依然会大得离谱。正确思路是错位切分先把所有矩形的x坐标收集起来排序去重。每两个相邻x坐标之间夹着一个垂直条带条带的宽度就是两个原始x坐标的差。由于条带两侧正好落在所有矩形的边界上任何一个矩形对某个条带只有两种状态完全包含这个条带矩形横跨L到R或者根本碰不到它。不存在“只盖住条带一半”的模棱两可。所以每个条带内部的任务变成一个一维问题收集所有横跨该条带的矩形把这些矩形的y方向区间拿出来做一遍区间合并合并出覆盖的总长度再乘以条带宽度就是该条带的覆盖面积。把所有条带的面积累加得到总面积。3.2 分步实现先切条带再做一维合并第一步收集所有矩形的x1、x2排序去重得到xs数组。第二步遍历xs的相邻元素对(xs[i], xs[i1])对每个条带扫描所有矩形如果rect.x1 xs[i] xs[i1] rect.x2说明矩形横跨整个条带把它的y区间(rect.y1, rect.y2)收集起来。第三步对这些y区间做区间合并计算覆盖高度然后累加height * (xs[i1] - xs[i])。这里有个关键细节宽度必须用原始坐标的差值而不是离散化后的下标差值。因为离散化丢掉了坐标之间“真实距离”的信息下标间隔1可能代表真实距离1也可能代表100000000必须回到原始坐标取值。3.3 完整代码与手工验证以下是可以直接编译运行的C代码#include bits/stdc.h using namespace std; using ll long long; struct Rect { ll x1, y1, x2, y2; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorRect rects(n); vectorll xs; for (auto r : rects) { cin r.x1 r.y1 r.x2 r.y2; xs.push_back(r.x1); xs.push_back(r.x2); } // 1. x坐标离散化 sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); ll ans 0; // 2. 枚举相邻x坐标构成的条带 for (int i 0; i 1 (int)xs.size(); i) { ll L xs[i], R xs[i 1]; ll width R - L; vectorpairll, ll segs; for (auto r : rects) { if (r.x1 L R r.x2) { segs.push_back({r.y1, r.y2}); } } if (segs.empty()) continue; // 3. 对y区间做合并 sort(segs.begin(), segs.end()); ll st segs[0].first, ed segs[0].second; ll cover_len 0; for (int j 1; j (int)segs.size(); j) { if (segs[j].first ed) { ed max(ed, segs[j].second); } else { cover_len ed - st; st segs[j].first; ed segs[j].second; } } cover_len ed - st; ans cover_len * width; } cout ans endl; return 0; }我拿一个经典样例验证过。三个矩形(0,0)-(2,2)、(1,1)-(3,3)、(2,0)-(4,2)。x坐标收集为0,1,2,3,4分成四个条带。条带[0,1]只有第一个矩形覆盖y区间[0,2]高度2面积2。条带[1,2]有前两个矩形覆盖y区间是[0,2]和[1,3]合并成[0,3]高度3面积3。条带[2,3]有后两个矩形覆盖y区间是[1,3]和[0,2]合并成[0,3]高度3面积3。条带[3,4]只有第三个矩形覆盖y区间[0,2]高度2面积2。总面积10和手工数矩形重叠区域得到的结果完全一致。4. 面试与竞赛中的高频变体和易错点4.1 各种五花八门的考察方式区间合并这题的变体非常多。LeetCode 56题“合并区间”就是裸模板题LeetCode 57题“插入区间”可以先把新区间插入原数组再合并LeetCode 759题“员工空闲时间”本质上是在多条时间轴上找覆盖次数为0的区间做法是把所有区间按左端点排序后合并再检查合并结果之间的空隙。离散化的变体更多。最常见的是“区间加值”给一个很大的数轴做N次区间加法最后查询某个位置的值。做法是收集所有区间的左右端点离散化后对相邻坐标之间的“段”做差分最后用前缀和恢复。还有一类题目把离散化和区间合并藏在更复杂的包装里比如给一堆矩形求周长、求多个区间的交集总长度、求某时间段内空闲区间等等。解题思路都有一个共同模式发现问题本质是“若干区间之间的关系计算”然后套上合并模板。4.2 典型踩坑现场汇总我用一张表把常见错误列清楚。这些坑我都踩过一遍写出来帮你少走弯路错误操作实际后果正确做法区间合并前忘记排序合并结果错乱左右端点乱跳任何合并操作前先按左端点排序用而不是判断重叠相邻区间不合并少算覆盖长度边界接触也算重叠用遍历结束后忘了push最后一个块答案正好少了最后一段区间循环结束后必须push_back({st, ed})用int存储坐标和面积数据一大直接溢出坐标和面积一律用long long离散化后用错映射方式坐标对应下标错误结果完全不可信用lower_bound二分映射确保返回值使用正确矩形条带覆盖判断写成L r.x1 R r.x2这类反向条件条带漏算或重复计算用r.x1 L R r.x2确认矩形完全覆盖条带这里面最隐蔽的是边界符号问题。区间合并如果处理的是“连续长度”两个区间只要端点接触就应该合并因为[1,2]和[2,3]合起来的连续覆盖长度确实是2。但如果题目统计的是“整数点的数量”[1,2]覆盖2个点[2,3]也覆盖2个点合并成[1,3]后是3个点而不是4个点这时合并条件就要用segs[i].first ed 1而不是 ed。具体用什么一定先想清楚题目要的是长度还是点数。4.3 排查问题时的调试技巧区间合并这类题出错时调试手段其实很朴素但不丢人。第一招把每次合并的中间结果用cerr打出来观察st和ed的更新轨迹是否符合预期。第二招自己构造几个极端样例所有区间共享一个端点、一个区间完全包含另一个区间、区间彼此相邻但不重合、只有一个区间。这四种情况基本能把代码run出八成的问题。第三招是最实在的写一个暴力解做对拍。暴力解法就是按坐标范围直接标记数组或直接按面积公式算数据量设小一点随机生成几十组数据把暴力解和优化解的输出逐一比对。一旦对拍出错把出错的随机数据唯一化手工推一遍就能定位。这套调试流程我至今还在用。很多时候不是算法不会是写出来总有那么一两处边界判断的细节不对对拍就是最直接的方式。5. 从坐标离散化到更广的领域5.1 差分数组与离散化的强力配合离散化最常见的搭档其实不是区间合并而是差分数组。看一个场景数轴坐标范围极大但只有N个区间操作每个操作给区间[L, R]加一个值v最后要一次性输出所有端点的值。照搬原始差分思路会死人因为数组根本开不下。做法是先离散化所有端点然后把“相邻离散点之间的整段区域”当作差分数组的元素。原始区间[L, R]映射成离散化下标后在下标区间上做差分。最后前缀和恢复时每段的值就是这一段内所有点的统一值。举个小例子坐标集合是{1, 3, 7, 12}离散化后下标0,1,2,3。对区间[3, 7]加1只需在离散化数组下标1到2之间做差分而不是在3到7的每个点上操作。这样数据规模被压缩到操作端点数量级复杂度立刻降下来。5.2 扫描线算法当离散化遇到更重的数据结构其实矩形面积并还有一种更进阶的解法叫扫描线。做法是把所有矩形的上下边拆成事件按y坐标扫描用线段树维护当前x方向的有效覆盖长度。扫描线算法和上面讲的“条带遍历法”核心一致都是先把一个维度离散化再对另一个维度做区间合并。区别只是扫描线用线段树把区间合并的复杂度降到了每次O(logN)整体复杂度从O(N^2logN)降到O(NlogN)。如果你在面试时写了条带遍历法面试官追问“能不能更快”答案就是扫描线。理解这条递进关系很重要不是两个割裂的算法而是同一个思想在不同数据结构支撑下的两种实现形式。5.3 “离散化”这个词在不同领域含义完全不同最后想提个容易混淆的问题。看到“离散化”三个字时注意它在不同领域的含义差别很大。算法竞赛和面试题里的离散化指的是坐标压缩把一个稀疏取值的大值域映射成紧凑下标。但在控制工程、电力电子领域比如SVPWM算法、多二阶广义积分器的讨论里离散化通常指的是把连续时间的微分方程转换成差分方程把模拟控制器变成数字控制器里的迭代公式。这两个意思差了十万八千里。如果你看到有人聊SVPWM算法时说“离散化”千万别把坐标压缩那套思路套进去。同样一个词两个圈子指代完全不同的操作。知道这个区别能避免不少沟通中的尴尬。我个人在实际操作中的体会是面试中遇到区间类问题看到坐标范围大到没法开数组第一反应就应该是离散化看到“合并区间”“区间覆盖总长”“求覆盖面积”这类字眼第一反应就应该是区间合并。很多时候把这两个词写进思维流程里再难的题也会有方向。最后分享一个练习技巧把那道矩形覆盖面积题反复敲三遍每遍不参考代码敲到能一口气完成为止。等这个熟练了你再看扫描线代码都不会犯怵。这算是踩坑踩出来的心得供每位读者参考。
