2019年秋招那会儿我还在学校刷题准备大厂笔试印象最深的就是华为这套Java笔试题。题目本身不算特别难但很讲究思路和代码功底尤其是第二道题考查的内容非常典型几乎把Java集合框架、排序、边界处理这些点都串起来了。这篇文章就专门复盘这道题从题目拆解、思路选型到最终实现把整条链路讲透。不管是正在准备校招笔试的同学还是想提升一下Java算法编码能力的朋友应该都能从里面捞到点干货。当时我是在牛客网上做的华为笔试三道题前面一道是常规的字符串处理这道排第二难度中等偏上。它的核心痛点在于题目给了一个很自然的业务场景但如果建模不清晰很容易被表面的复杂度绕进去。而这道题最巧的地方是它本质上考察的是一个非常经典的算法思想——差分数组。1. 题目拆解与核心思路1.1 题目原型与真实应用场景先把题目还原一下输入若干任务每个任务包含开始时间、结束时间以及该任务运行期间占用的资源数量要求计算整个时间轴上资源占用的最大峰值。举个例子3 1 3 2 2 5 3 4 6 1三个任务第一个任务从时间1到3占用2个资源第二个从2到5占用3个资源第三个从4到6占用1个资源。那么整个过程中资源占用峰值是多少这道题看起来像是一道普通的区间问题但它的原型在真实业务里非常常见。云计算平台的资源调度系统、公司内部的排班系统、视频直播服务的并发观看人数统计——本质都是同一类问题一堆带权重的区间求任意时刻的累计最大权重。华为笔试考这种题说白了就是在考察候选人的建模能力和数据结构功底。很多人在看到区间时就条件反射想到线段树或者扫描线但在这道题的数据规模下线段树其实有点杀鸡用牛刀而且写起来容易出错。更自然的解法是差分数组。1.2 为什么选差分数组而不是时间轴模拟我第一次做这道题时最直觉的想法是开一个大数组从最小时间遍历到最大时间每个时间点把所有覆盖该点的任务资源加起来取最大值。这种做法在时间范围很小的时候确实可行复杂度是O(T * N)跟时间轴长度成正比。但问题在于题目并没有保证时间范围是有限的。如果任务的开始时间最大到10的9次方开数组那就是宣告死刑。就算能开出来遍历一遍也是天文数字。差分数组的思路完全不一样。它不关心时间轴上每个具体时刻只关心“状态发生变化的边界点”。一个任务开始资源增加一个任务结束资源减少。我们只需要把变化记录下来然后按时间顺序累加就能找回任意时刻的真实占用值。用生活化的例子解释酒店前台登记入住和退房。有人入住房间占用数加1有人退房房间占用数减1。前台不需要每分钟都数一遍房间只需要知道每个入住/退房节点导致的房间数变化然后顺着时间线往后推算任何时刻住了多少间房都一清二楚。这就是差分数组的精髓把区间更新的操作优化成只记录起点和终点两个事件点。复杂度从O(T * N)直接降到O(N log N)——需要排序所以要带个log。1.3 数据结构选型TreeMap还是HashMap思路确定了接下来的问题是用什么数据结构来存这些“事件点”。这里有个很容易忽略的细节事件点必须按时间顺序处理所以我们需要一个有序的容器。有同学第一反应是HashMap存下每个时间点的净变化量最后再调Map.Entry排序。这样当然也能做但代码会绕一道而且排序的时候还得自己写比较器笔试场景下属于给自己加戏。直接上TreeMap原因有三按键自然升序排列遍历顺序就是时间线顺序不用额外排序提供了merge方法可以一行代码完成“累加或插入”代码非常简洁后续如果需要查某个时间点前后的状态floorEntry、ceilingEntry这些方法都是现成的我见过不少人在这种场景下选了HashMap然后排序时因为比较器写错或者没有考虑null值导致全盘崩溃。还有一个更隐性的问题如果两个事件点完全相同HashMap会覆盖而TreeMap配合merge可以完美合并累加。所以这道题用TreeMap不是“可以”而是“更合适”。2. 输入解析与数据预处理确定了思路接下来要处理的就是输入。很多同学笔试翻车不是死在算法上而是死在输入解析上华为笔试用的是牛客网的OJ系统不同题目对输入格式的要求还不一样这里值得好好拆一下。2.1 华为笔试的两种输入模式第一种是核心代码模式也就是题目已经帮你把参数解析好了你只需要实现一个函数。这种情况下输入通常是一个二维数组比如int[][] tasks每个元素是{start, end, resource}。第二种是ACM模式需要你自己从标准输入里读数据。华为的笔试偶尔会用这种模式你需要在main函数里通过Scanner或者BufferReader把数据读进来再处理。很多人平时刷LeetCode习惯了核心代码模式一到ACM模式就懵。我见过有人直接Scanner.next()读一行字符串然后拿split切结果遇到换行符和空格混排的数据就乱掉。这道题如果走ACM模式输入通常是第一行任务个数N 后面N行每行三个整数表示开始时间、结束时间、占用资源数解析的方式很简单用BufferedReader逐行读然后对每一行split( )就行。需要特别注意多组测试用例时hasNextLine()的判断条件不能写错否则会有空行读取的问题。2.2 字符串转二维数组的三种写法如果是核心代码模式传进来的是二维数组还好。但有的时候牛客会把输入作为字符串给你那就需要自己转。第一种方法用split加Integer.parseInt这是最直接的方式String input [[1,3,2],[2,5,3],[4,6,1]]; String[] parts input.substring(2, input.length() - 2).split(\\],\\[); int n parts.length; int[][] tasks new int[n][3]; for (int i 0; i n; i) { String[] nums parts[i].split(,); tasks[i][0] Integer.parseInt(nums[0]); tasks[i][1] Integer.parseInt(nums[1]); tasks[i][2] Integer.parseInt(nums[2]); }第二种方法是用正则表达式提取所有数字Matcher m Pattern.compile(\\d).matcher(input); ListInteger nums new ArrayList(); while (m.find()) { nums.add(Integer.parseInt(m.group())); }第三种方法是直接JSON解析用Jackson或Gson库int[][] tasks new ObjectMapper().readValue(input, int[][].class);笔试场景下我推荐第一种简单直接不依赖额外库也不会因为正则写错而浪费时间。正则方案看着酷但\d会把三位数拆开需要额外处理笔试的时候容易翻车。2.3 数据预处理中的边界问题这道题最关键的一个边界问题就是任务的结束时间到底是开区间还是闭区间也就是说一个任务从1到3到底在时间3还占不占用资源华为这道题原题用的是“结束时间之后释放资源”的设定也就是结束时间点本身不占用资源。这个设定很符合直觉——就好比你退房那天不会继续占着那间房。但如果不仔细审题很容易把结束时间当成闭区间仍然计数导致结果偏大。在差分数组实现里开区间和闭区间只差一个符号如果是开区间任务的资源占用范围是[start, end)在差分数组上表现为start处加end处减如果是闭区间[start, end]就要在end 1处减。这个细节不搞清楚输出就会差1。另外还有一个很容易忽略的坑任务结束时间等于开始时间。比如5 5 3这种任务实际上瞬间开始瞬间结束占用时间为零。在差分数组里start和end是同一个点加3减3直接抵消峰值不会受影响这种情况代码要能正确处理不能因为遍历时merge了两次而产生错误状态。3. 核心逻辑实现与代码详解数据解析完了思路也清晰了就到了最核心的代码实现环节。这里我给出两种可行方案分别对应不同的笔试状态和个人习惯。3.1 用TreeMap实现离散化差分完整的核心代码可以这么写import java.util.Map; import java.util.TreeMap; public class Main { public static void main(String[] args) { // 构造测试数据三个任务格式为 {开始时间, 结束时间, 资源数} int[][] tasks { {1, 3, 2}, {2, 5, 3}, {4, 6, 1} }; System.out.println(maxResourcePeak(tasks)); } public static long maxResourcePeak(int[][] tasks) { if (tasks null || tasks.length 0) { return 0; } // key为时间点value为净变化量 TreeMapInteger, Integer diff new TreeMap(); for (int[] task : tasks) { int start task[0]; int end task[1]; // 开区间end时刻释放资源 int resource task[2]; diff.merge(start, resource, Integer::sum); diff.merge(end, -resource, Integer::sum); } long current 0; long max 0; for (Map.EntryInteger, Integer entry : diff.entrySet()) { current entry.getValue(); max Math.max(max, current); } return max; } }这里重点说几个细节。第一diff.merge(start, resource, Integer::sum)这行代码的含义是如果start这个键不存在就插入resource如果已经存在就把原来的值加上resource。这样处理两个任务从同一个时间点开始时两个增量会正确累加。如果不用merge写代码会长这样diff.put(start, diff.getOrDefault(start, 0) resource);两行变一行而且不会有自动装箱拆箱的隐患。第二为什么返回值用long而不是int因为需要考虑极限情况如果任务数量达到10的5次方每个任务资源数是10的9次方那么峰值可能超过int的最大值。虽然题目大概率不会这么变态但用long是无脑安全的。笔试中因为溢出丢分的真的是大意失荆州。第三遍历的时候为什么current entry.getValue()而不需要判断时间先后因为TreeMap天生按键升序排列遍历顺序就是时间先后顺序。这正是选TreeMap的原因所在。3.2 笔试现场方案优先队列贪心模拟如果用TreeMap是“事件驱动”的思路那优先队列就是“区间扫描”的思路有异曲同工之妙。思路是先把所有任务按开始时间排序然后遍历每个任务用一个优先队列最小堆来维护当前正在进行的所有任务的结束时间。每遍历到一个新任务时先把所有结束时间早于当前任务开始时间的任务弹出因为那些任务已经结束了然后当前任务入队同时计算当前所有在队任务的资源总和。import java.util.Arrays; import java.util.PriorityQueue; public class Main { static class Task { int start; int end; int resource; Task(int start, int end, int resource) { this.start start; this.end end; this.resource resource; } } public static void main(String[] args) { int[][] data { {1, 3, 2}, {2, 5, 3}, {4, 6, 1} }; int n data.length; Task[] tasks new Task[n]; for (int i 0; i n; i) { tasks[i] new Task(data[i][0], data[i][1], data[i][2]); } Arrays.sort(tasks, (a, b) - a.start - b.start); // 优先队列按结束时间升序 PriorityQueueTask pq new PriorityQueue((a, b) - a.end - b.end); long max 0; long current 0; for (Task task : tasks) { // 所有结束时间早于当前任务开始时间的任务出队 while (!pq.isEmpty() pq.peek().end task.start) { current - pq.poll().resource; } pq.offer(task); current task.resource; max Math.max(max, current); } System.out.println(max); } }注意这段代码里pq.peek().end task.start用的是小于等于因为结束时间是开区间当前任务开始时所有已经结束的任务都必须释放资源。如果把这里写成就会导致同一时刻的资源重复计算答案直接不对。这两种解法的复杂度都是O(n log n)从笔试角度都能过。哪个更好我自己写的话更倾向于TreeMap的差分方案因为它不需要自定义数据结构代码量少逻辑直观不容易在优先队列的比较器上翻车。优先队列方案的优点是如果你对区间问题比较熟写起来也很顺手。笔试时选择你练得最熟的那个就好。3.3 复杂度分析与面试官追问做完这道题不要急着交卷。如果你是在面试现场写这道题面试官大概率会追问几个延伸问题提前想好能加分不少。第一个问题为什么差分数组的复杂度是O(n log n)而不是O(n)因为TreeMap的merge操作底层是红黑树单次操作复杂度O(log n)一共n个任务每个任务会产生两个事件所以总复杂度O(n log n)。如果你用HashMap加最后排序的方案复杂度其实也是O(n log n)只是常数上稍微小一点但代码变复杂了不划算。第二个问题如果时间范围不超过10的5次方能不能用普通数组可以。直接用数组下标表示时间点diff[start] resource; diff[end] - resource;最后遍历一遍数组取前缀和最大值。这样复杂度是O(n T)比TreeMap快很多。但是同样要注意如果T太大数组会开不下。所以普通数组可以作为一种特化优化但差分思想的本质是一样的。第三个问题如果不仅要输出峰值还要输出峰值出现的时刻代码怎么改很简单在遍历过程中当current更新为新的最大值时记录下当前的entry.getKey()那就是峰值第一次出现的时刻。如果要求所有出现峰值的时刻就需要在等于最大值时继续记录。这个追问其实是在考察你有没有真正理解算法而不是背代码。差分数组的本质就是状态变化记录理解了这点怎么变形都是家常便饭。4. 常见问题与排查技巧实录4.1 我刷这道题时踩过的三个坑第一个坑是并发修改异常。当时我图省事想用HashMap存储差分数据然后遍历的时候做处理代码如下for (Integer key : map.keySet()) { // 在这个循环里对map进行了put操作 }结果直接抛了ConcurrentModificationException。原因是在遍历HashMap的keySet时修改了map结构。后来改用TreeMap的entrySet遍历同样的问题依然存在因为遍历过程中merge又往里插入了新键。正确的做法是先记录所有键值对或者干脆在初始化时就把数据全部merge完成再遍历不要在遍历过程中修改结构。第二个坑是开闭区间判断失误。第一次用差分实现的时候我下意识写了end 1才减因为之前做过闭区间版本的区间合并题。结果答案是错的而且差的值不固定调试了很久才意识到题目里结束时间是开区间。从那以后每次做区间题我都会在草稿纸上先写清楚[start, end)还是[start, end]再动手写代码。第三个坑是用Integer做累加时超出最大值。当时我用int current累加测试数据量大的时候直接溢出变成负数最大值比较直接失效。排查了半天才想到用long。现在我的习惯是只要涉及累加的场景哪怕是看起来不可能会超也统一用long。4.2 本地跑得好好的OJ一提交就错这种情况在牛客上特别常见。明明本地IDE测试没问题一提交就显示“答案错误”或者“段错误”原因多半出在输入输出处理上而不是核心算法。几个高频雷区可能问题现象解决方案类名不是Main编译错误牛客Java类名必须是Main且不能有package没有处理多组输入读取不全或死循环用while (scanner.hasNext())包裹处理逻辑输出多了调试信息答案错误提交前注释掉所有System.out.println调试语句导入缺失编译错误使用Arrays、Map等必须写对应import读入时用了next()而不是nextLine()输入错位先确认输入是纯数字行再用next()或nextInt()还有一个很多人不注意的如果题目是多组测试用例Scanner用hasNextLine()判断时可能因为最后一行是空行导致多循环一次输出一个多余的换行或者报错。更稳妥的方式是用hasNext()判断是否有下一个整数而不是判断行。4.3 这份代码能怎么搬到真实项目里笔试归笔试但代码的思路完全可以迁移到真实业务中。我后来在公司做直播平台的资源预估时就遇到过几乎一模一样的问题用户进入直播间是“开始事件”离开是“结束事件”每个用户占用一定带宽资源需要估算某个时间段的服务带宽峰值。当时我直接把这道题的解法搬过去只不过把TreeMap改成了MySQL事件表把内存中的事件点变成了数据库里带timestamp和delta的记录聚合查询用的SQL而不是Java遍历。但核心思路没有任何变化只记录状态变化的边界点然后按时间顺序累加。这种抽象能力才是刷题最大的收获。题目会变场景会变但“区间加权重求峰值”这个模型始终在那里。下次你再遇到会议室预订冲突检测、优惠券使用时段统计、在线课程同时观看人数监控都可以用这个套路来打。最后再分享一个我在秋招季总结出来的心得笔试前与其盲目刷一百道新题不如把经典题型的模板练到条件反射。这道题背后是差分思想面试官拿它来区分“背题人”和“懂题人”。如果只是背下TreeMap那几行代码换个包装就懵了但如果你真的理解了“边界事件”这四个字无论题目怎么变你都能在五分钟内给出方案。这个能力才是校招笔试真正要考的东西。