华为OD机试核心：差分数组与前缀和算法精解

1. 项目概述从一道“小火车”题看华为OD机试的核心逻辑最近在帮几个准备华为OD机试的朋友做模拟练习发现他们普遍对“人数最多的站点”这类题目感到头疼。这道题在各大论坛和备考资料里出镜率极高常被冠以“小火车最多人时所在园区站点”这样生活化的描述。乍一看题目场景很简单一列园区小火车在固定线路上循环运行员工们在不同的站点上车和下车我们需要找出在某个时刻车上人数最多的那个站点是哪里。很多新手朋友的第一反应是“这不就是模拟一下上下车过程然后找最大值吗”理论上没错但真动手写起来尤其是在机试那种紧张、限时的环境下从理解题意到设计出高效、正确的解法中间隔着好几道坎。这道题之所以经典是因为它完美地覆盖了华为OD机试的几个核心考察点对问题本质的抽象能力、边界条件的缜密思考、以及对基础数据结构的灵活运用。它不像纯算法题那样需要艰深的数学推导更像是一道“工程思维”应用题。你能否快速地将“站点”、“上下车”这些业务语言翻译成程序世界里的“数组下标”、“区间操作”和“前缀和”决定了你解题的速度和代码的优雅程度。更关键的是题目描述中可能隐藏的“循环线路”、“上下车记录可能无序”、“多人同时同站上下车”等细节都是筛选候选人的隐形门槛。接下来我就结合自己带人刷题和面试官交流的经验把这道题里里外外拆解清楚并提供C、Java、Python、C、JS五种语言的实现参考希望能帮你不仅“做出”这道题更能“吃透”这类题的解题心法。2. 核心思路拆解化繁为简的“事件记录”与“前缀和”思想面对“人数最多的站点”最直接的暴力解法是什么模拟每一趟车的运行在每个站点根据上下车记录更新人数最后遍历所有站点找最大值。如果线路不长、记录不多这方法勉强可行。但一旦数据量上来比如站点数N上万记录数M也上万这种模拟每一时刻的复杂度可能接近O(N*M)在机试中极易超时。因此我们必须寻找更聪明的办法。2.1 关键问题抽象从“模拟过程”到“处理事件”这道题的精髓在于我们其实不需要关心火车具体是怎么一圈圈跑的。我们只关心在哪个站点人数发生了怎样的变化。每一对(start, end)上下车记录本质上定义了一个区间从start站上车到end站下车。这意味着从start站包含开始车上人数增加了一人到了end站包含车上人数减少一人。注意这里有一个常见的理解误区乘客在end站下车所以人数是在end站减少的而不是在end的下一站。于是整个问题被抽象为我们有n个站点编号通常为1到n。我们有一系列m条“事件”在站点s发生一次“人数1”在站点e发生一次“人数-1”。我们需要计算从站点1开始到站点n结束每个站点上“净人数”的变化情况并找出累计人数最大的站点。这里的“净人数”变化就是通过处理这些“1”和“-1”事件得到的。2.2 高效算法选择差分数组与前缀和如何高效地处理这些区间上的增减操作这就是差分数组大显身手的时候。差分数组diff[]diff[i]表示站点i与站点i-1的人数差值。初始时所有diff[i] 0。区间操作对于一条从start到end的乘车记录假设start end在start站人数比前一站增加了1所以diff[start] 1。在end站乘客下车人数比前一站减少了1。注意乘客在end站下车所以从end1站开始人数才减少。因此我们需要执行diff[end 1] - 1。如果end是最后一个站点则end1可能越界需要特殊处理通常忽略或使用长度为n2的数组。还原真实人数得到差分数组后我们通过计算前缀和就能得到每个站点的实际人数。设count[0] 0(或根据题意初始车上人数为0)。对于i从 1 到 ncount[i] count[i-1] diff[i]。这个count[i]就代表了火车到达站点i时在站点i的上下车发生之后车上的总人数。这个算法的美妙之处在于它将m次区间更新操作压缩成了2m次单点操作更新diff数组最后通过一次O(n)的前缀和扫描就能得到结果。总时间复杂度为O(m n)空间复杂度为O(n)非常高效。2.3 边界与难点循环线路的处理题目描述如果是“园区循环线路”那么start可能大于end。例如员工从站点7上车到站点2下车这意味着火车穿过了终点站又回到了起点。 处理这种情况有两种主流方法拆分成两个区间将(7, 2)的记录拆分成(7, n)和(1, 2)。即从7站坐到终点站n下车人数在7站1在n站-1同时另一个人从1站坐到2站下车人数在1站1在2站-1。这相当于把环拆成了线。统一偏移法更巧妙的做法是我们依然只记录diff[start] 1和diff[end 1] - 1。但当start end时我们意识到这次乘车经过了“零点”使得整个环形线路上的基础负载增加了1人。我们可以额外维护一个base变量当遇到start end时base 1。最后在计算每个站点人数时实际人数是base count[i]。这里的count[i]是由所有start end的记录计算出的前缀和。这种方法更简洁但理解起来需要绕个弯。在机试中如果题目明确是环形方法一拆分法更直观不易出错也更容易向面试官解释。我们后续的代码实现将主要基于这种方法。注意务必仔细阅读题目输入输出说明。站点编号是从0开始还是1开始输入记录是否保证start不等于end输出要求是输出站点编号还是最大人数还是都要如果最大人数相同的站点有多个是输出第一个、最后一个、还是所有这些细节直接决定了你代码的边界处理和最终结果。3. 多语言代码实现与逐行解析理解了核心算法我们来看看如何用不同语言实现。我会提供清晰的代码并附上关键行的解析。我们假设题目输入格式为第一行是站点数n第二行是记录数m随后m行每行是两个整数start和end代表一条乘车记录。站点编号为1到n。输出人数最多的站点编号假设只输出一个如果并列则输出编号最小的。3.1 C 实现#include iostream #include vector #include algorithm using namespace std; int main() { int n, m; cin n m; // 差分数组多开两个空间方便处理 end1 可能等于 n1 的情况 vectorint diff(n 2, 0); for (int i 0; i m; i) { int start, end; cin start end; // 处理环形线路如果 start end是正常区间 if (start end) { diff[start] 1; diff[end 1] - 1; // 注意是 end1 } else { // start end说明跨过了终点拆分成两段 // 第一段[start, n] diff[start] 1; diff[n 1] - 1; // 终点站的下一个“虚拟站” // 第二段[1, end] diff[1] 1; diff[end 1] - 1; } } // 计算前缀和找出最大人数及其站点 int currentPassengers 0; int maxPassengers -1; int maxStation 1; for (int i 1; i n; i) { currentPassengers diff[i]; // 注意比较逻辑只有当当前人数严格大于历史最大时才更新站点。 // 这样可以保证在人数相同时保留编号更小的站点。 if (currentPassengers maxPassengers) { maxPassengers currentPassengers; maxStation i; } } cout maxStation endl; // 如果题目要求也输出人数可以加上cout maxPassengers endl; return 0; }代码解析与避坑点vectorint diff(n 2, 0);分配n2个空间。diff[1]到diff[n]对应站点1到ndiff[n1]用于安全地处理diff[end1]当endn的情况。这是避免数组越界的常用技巧。if (start end)这是处理环形问题的核心判断。else分支实现了拆分操作。diff[n 1] - 1;在拆分的第一段乘客在站点n下车所以diff[n1]记录了这个减少。虽然n1超出了实际站点范围但在我们计算前缀和到in时这个-1已经被累加进去了不影响1到n的结果。diff[n1]本身不会被访问。if (currentPassengers maxPassengers)使用而不是确保了当最大人数并列时记录的是第一个达到该最大值的站点因为i是从小到大遍历的。如果题目要求输出最后一个则条件应改为。3.2 Java 实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n scanner.nextInt(); int m scanner.nextInt(); // 差分数组索引0不使用从1开始 int[] diff new int[n 2]; for (int i 0; i m; i) { int start scanner.nextInt(); int end scanner.nextInt(); if (start end) { diff[start] 1; // 防止 end1 索引越界但我们的数组大小是 n2end 最大为 n所以 end1 n1安全。 diff[end 1] - 1; } else { // 环形处理拆分 diff[start] 1; diff[n 1] - 1; // 第一段在虚拟的n1站结束 diff[1] 1; // 第二段从1站开始 diff[end 1] - 1; } } int currentPassengers 0; int maxPassengers -1; int maxStation 1; for (int i 1; i n; i) { currentPassengers diff[i]; if (currentPassengers maxPassengers) { maxPassengers currentPassengers; maxStation i; } } System.out.println(maxStation); scanner.close(); } }Java特有注意事项Scanner类用于输入比较方便但在处理大数据量时性能不如BufferedReader。不过对于OD机试的常规数据量Scanner完全足够。数组初始化int[] diff new int[n 2];Java会默认初始化为0。逻辑与C版本完全一致。注意在OJ上类名必须为Main。3.3 Python 实现def main(): import sys data sys.stdin.read().strip().split() if not data: return it iter(data) n int(next(it)) m int(next(it)) # 差分数组长度为 n2索引0占位不用 diff [0] * (n 2) for _ in range(m): start int(next(it)) end int(next(it)) if start end: diff[start] 1 # 同样end最大为nend1最大为n1数组长度n2是足够的 diff[end 1] - 1 else: # 处理环形 diff[start] 1 diff[n 1] - 1 diff[1] 1 diff[end 1] - 1 current_passengers 0 max_passengers -1 max_station 1 for i in range(1, n 1): current_passengers diff[i] if current_passengers max_passengers: max_passengers current_passengers max_station i print(max_station) if __name__ __main__: main()Python实现技巧与坑点sys.stdin.read()一次性读取所有输入在处理大量数据时比input()逐行读取更快是Python在算法竞赛中的标准做法。iter(data)和next(it)将拆分后的字符串列表转换为迭代器依次获取整数比用索引访问更优雅。列表初始化diff [0] * (n 2)这是创建列表并初始化为0的高效写法。性能提醒Python的循环相比C/Java较慢但此算法复杂度为O(mn)对于OD机试的典型数据规模n, m 10^5Python是完全可以通过的。关键在于使用高效的输入输出。3.4 C语言实现#include stdio.h #include stdlib.h int main() { int n, m; scanf(%d %d, n, m); // 动态分配差分数组并初始化为0 int *diff (int*)calloc(n 2, sizeof(int)); for (int i 0; i m; i) { int start, end; scanf(%d %d, start, end); if (start end) { diff[start] 1; diff[end 1] - 1; } else { // 环形拆分 diff[start] 1; diff[n 1] - 1; diff[1] 1; diff[end 1] - 1; } } int currentPassengers 0; int maxPassengers -1; int maxStation 1; for (int i 1; i n; i) { currentPassengers diff[i]; if (currentPassengers maxPassengers) { maxPassengers currentPassengers; maxStation i; } } printf(%d\n, maxStation); // 释放动态分配的内存 free(diff); return 0; }C语言注意事项callocvsmalloc使用calloc可以在分配内存的同时将其初始化为0比malloc后手动用循环赋值更简洁高效。数组索引C语言数组下标从0开始但我们依然使用diff[1]到diff[n]因此分配n2个空间diff[0]闲置不用。这样逻辑上与其他语言保持一致更清晰。内存释放虽然对于小程序不释放内存程序结束也会回收但养成free的好习惯是专业性的体现。3.5 JavaScript (Node.js) 实现const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let inputLines []; rl.on(line, (line) { inputLines.push(line); }).on(close, () { solve(inputLines); }); function solve(lines) { // 解析第一行n 和 m const firstLine lines[0].split( ).map(Number); const n firstLine[0]; const m firstLine[1]; // 初始化差分数组索引0占位 const diff new Array(n 2).fill(0); // 解析后续的 m 行记录 for (let i 1; i m; i) { const [start, end] lines[i].split( ).map(Number); if (start end) { diff[start] 1; diff[end 1] - 1; } else { // 处理环形线路 diff[start] 1; diff[n 1] - 1; diff[1] 1; diff[end 1] - 1; } } let currentPassengers 0; let maxPassengers -1; let maxStation 1; for (let i 1; i n; i) { currentPassengers diff[i]; if (currentPassengers maxPassengers) { maxPassengers currentPassengers; maxStation i; } } console.log(maxStation); }JavaScript/Node.js 环境要点输入处理Node.js没有标准输入流暂停通常通过readline模块逐行读取。这里将所有行存入数组在close事件中统一处理。new Array(n2).fill(0)这是创建并填充数组的简洁方法。lines[i].split( ).map(Number)将字符串行分割并转换为数字数组是常见的解析方式。逻辑与其他语言无异。需要注意在有些在线判题环境中可能需要使用require(fs).readFileSync(0, utf-8)来同步读取全部输入具体要看环境要求。4. 常见变种、陷阱与调试技巧在实际做题或面试中题目不会总是直白地给出“站点”和“上下车”。它可能会换各种“马甲”但内核不变。4.1 经典变种题型会议室安排 II给你若干会议的时间区间[start_i, end_i)问至少需要多少个会议室。这其实就是找同一时刻进行的最大会议数量。把每个会议看成一个人在start_i时刻进入会议室人数1在end_i时刻离开人数-1。解法一模一样。航班预订统计有n个航班预订记录bookings[i] [first_i, last_i, seats_i]表示从first_i到last_i的每个航班都增加了seats_i个座位。求每个航班最终的总预订数。这是差分数组最直接的应用diff[first_i] seats_i,diff[last_i 1] - seats_i。公交路线乘客数与本题几乎一致只是上下文换成了公交站。识别这类题的关键是问题是否涉及对多个区间进行统一的增减操作并最终询问每个点的状态如人数、数量、总和等。4.2 高频易错点避坑指南下标从0还是1开始这是最经典的错误。题目描述、你的差分数组定义、循环范围必须统一。如果站点编号是0到n-1那么差分数组长度应为n1操作时diff[end]而不是end1要减1因为end站下车后从end站开始人数就减少了。务必在动笔前用一个小例子比如2个站点1条记录在纸上演算一遍。环形处理逻辑错误拆分时第二段的起点是1不是start。很多人会错误地写成diff[1] 1; diff[start] - 1;。记住拆分后是两条独立的记录(start, n)和(1, end)。初始化与更新顺序差分数组diff必须初始化为0。在计算前缀和时currentPassengers的初始值通常是0表示初始空车。如果题目说初始有若干人则需要将currentPassengers初始化为该值或者等价地将diff[1]加上初始人数。最大值的初始值maxPassengers初始化为-1可以正确处理车上可能一直为0人的情况。如果初始化为0当所有站点人数都是0时maxStation不会被更新因为currentPassengers maxPassengers条件不成立可能导致输出错误如默认的maxStation1但可能正确答案是站点1或其他。初始化为-1确保了0 -1成立。并列情况处理如前所述使用还是取决于题目要求。如果不明确可以在注释中说明你的假设或者按照“输出最小编号”的常见约定使用。4.3 调试与测试用例设计自己编写测试用例是验证代码正确性的最好方法。基础测试输入n3, m2, 记录[[1,2], [2,3]]预期站点2人数最多2人。模拟1站上1人 - 2站1号下2号上人数1 - 3站2号下人数0。站点2人数为1等等这里有个关键按照我们的定义diff[2]对应站点2的变化count[2]是到达站点2后的人数。对于记录(1,2)diff[1]1, diff[3]-1。对于(2,3)diff[2]1, diff[4]-1。计算前缀和count[1]1, count[2]112, count[3]2-11。所以最大人数2在站点2。正确。环形测试输入n5, m2, 记录[[4,2], [1,3]]手动模拟记录1从4坐到2环形。可以认为有1个人从4坐到51同时另一个人从1坐到21。记录2从1坐到31。所以站点1记录2的1和记录1拆分的第二段1共2等等需要系统计算。 拆分(4,2)为(4,5)和(1,2)。 最终操作diff[4]1, diff[6]-1; diff[1]1, diff[3]-1;(来自拆分)diff[1]1, diff[4]-1;(来自(1,3)) 合并diff[1]2, diff[3]-1, diff[4]1-10, diff[6]-1。 计算count:count[1]2, count[2]2, count[3]2-11, count[4]1, count[5]1。 最大人数2在站点1和2。按我们的代码输出站点1。边界测试n1, m0空车输出站点1人数0。n1, m1, 记录[[1,1]]这是什么原地上下车需要看题目定义。通常这种记录无效或表示该站无人变化。我们的代码会执行diff[1]1, diff[2]-1计算count[1]1。如果题目不允许startend需要在输入时过滤。大数量测试n100000, m100000随机生成记录确保程序不超时、不溢出。在本地IDE中可以用这些用例逐行调试观察diff数组和count即currentPassengers的变化过程这是理解算法最直观的方式。5. 从解题到举一反三差分数组的深入理解与应用扩展通过这道题我们深入使用了差分数组。但差分数组的魅力远不止于此。它的核心思想是将对区间[l, r]的批量操作如同时加一个值c转化为对端点l和r1的两个单点操作。这能将O(区间长度)的操作降为O(1)。5.1 差分与前缀和的互逆关系差分是前缀和的逆运算。前缀和数组pre[i] arr[1] arr[2] ... arr[i]。差分数组diff[i] arr[i] - arr[i-1](对于i1)且diff[1] arr[1]。对arr的区间[l, r]加c等价于对diff进行diff[l] c,diff[r1] - c。对diff求前缀和就能得到操作后的arr。理解这个互逆关系你就能自己推导出算法而不是死记硬背。5.2 更高维度的应用差分可以推广到二维甚至三维。例如在二维矩阵中如何快速给一个子矩形区域内的所有元素加上一个常数c定义二维差分数组diff[x][y]。对于矩形区域(x1, y1)到(x2, y2)的c操作可以转化为四个单点操作diff[x1][y1] cdiff[x21][y1] - cdiff[x1][y21] - cdiff[x21][y21] c最后对diff做二维前缀和就能得到更新后的原矩阵。这个技巧在解决一些矩阵更新、子矩阵求和的问题时能将复杂度从O(n²)或O(n³)降到O(n)或O(n²)。5.3 在华为OD机试中的战略地位华为OD机试的题目库虽然庞大但题型和知识点是相对固定的。“人数最多的站点”所属的“区间问题/差分前缀和”类别是高频考点之一。与之并列的高频考点还包括字符串处理、哈希映射、双指针、滑动窗口、深度/广度优先搜索、动态规划、二叉树遍历等。准备机试时我的建议是分专题突破像今天这样把一道经典题吃透理解其各种变种。差分数组专题就练这道题和“航班预订统计”、“会议室II”足矣。熟练度至上对于核心算法要达到能闭着眼睛、在10-15分钟内写出无bug代码的程度。这需要反复练习尤其是用你选择的主语言C/Java/Python。模拟实战用过去几年的真题进行全真模拟严格计时锻炼在压力下分析题目、设计算法、编写调试的能力。重视边界机试的测试用例一定会包含各种边界情况。养成在编码前就先思考边界空输入、极值、重复、无序等的习惯并在代码中体现出来。这道“小火车”题就像一把钥匙帮你打开了“差分数组”和“区间扫描”这类问题的大门。掌握了它再遇到类似的场景你就能立刻反应过来快速构建出高效解法的框架。编程面试和考试很多时候考察的就是这种将实际问题抽象为已知模型的能力。希望这篇长文不仅能帮你解决这一道题更能为你提供一种解决问题的思路和持续学习的方法。