华为Java笔试题复盘：用差分数组与TreeMap解资源峰值计算

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); List<Integer> 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为净变化量 TreeMap<Integer, 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.Entry<Integer, 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); // 优先队列按结束时间升序 PriorityQueue<Task> 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测试没问题，一提交就显示“答案错误”或者“段错误”，原因多半出在输入输出处理上，而不是核心算法。

几个高频雷区：

还有一个很多人不注意的：如果题目是多组测试用例，Scanner用hasNextLine()判断时，可能因为最后一行是空行导致多循环一次，输出一个多余的换行或者报错。更稳妥的方式是用hasNext()判断是否有下一个整数，而不是判断行。

4.3 这份代码能怎么搬到真实项目里

笔试归笔试，但代码的思路完全可以迁移到真实业务中。我后来在公司做直播平台的资源预估时，就遇到过几乎一模一样的问题：用户进入直播间是“开始事件”，离开是“结束事件”，每个用户占用一定带宽资源，需要估算某个时间段的服务带宽峰值。

当时我直接把这道题的解法搬过去，只不过把TreeMap改成了MySQL事件表，把内存中的事件点变成了数据库里带timestamp和delta的记录，聚合查询用的SQL而不是Java遍历。但核心思路没有任何变化：只记录状态变化的边界点，然后按时间顺序累加。

这种抽象能力才是刷题最大的收获。题目会变，场景会变，但“区间加权重求峰值”这个模型始终在那里。下次你再遇到会议室预订冲突检测、优惠券使用时段统计、在线课程同时观看人数监控，都可以用这个套路来打。

最后再分享一个我在秋招季总结出来的心得：笔试前与其盲目刷一百道新题，不如把经典题型的模板练到条件反射。这道题背后是差分思想，面试官拿它来区分“背题人”和“懂题人”。如果只是背下TreeMap那几行代码，换个包装就懵了；但如果你真的理解了“边界事件”这四个字，无论题目怎么变，你都能在五分钟内给出方案。这个能力，才是校招笔试真正要考的东西。