先说我看到这道题第一反应这不就是“积木大赛/铺设道路”的换皮题吗如果你刷过洛谷 P1969 或者 P5019看到“搭房子”这三个字应该直接条件反射出解法。2026 蚂蚁春招开发岗 3 月 15 日这套卷子我没法确认全部内容但“搭房子”这个题面在算法圈里实在太经典了几乎可以 1:1 映射到给定目标高度数组初始所有位置高度为 0每次操作选择一个连续区间整体 1求最少操作次数。这篇文章把四件事讲透题目到底在说什么、正确思路是怎么推出来的、Java/C/Python 三种写法怎么选、以及去哪里在线验证你的代码。全文不搞花活全是能直接抄进 IDE 的东西。1. 题目快览与核心思路破题先把题目标准化。有一排 n 个位置每个位置有一个目标高度 h[i]。所有位置初始高度都是 0。你每次可以选择一段连续的位置 [l, r]把这段区间内所有位置的高度同时加 1。问最少需要多少次操作才能让所有位置都达到目标高度这个形式可能和你看到的原题措辞略有出入比如有的版本会说“每次搭一层楼必须连续”有的版本会说“用木板铺地基”但数学模型完全一样。如果原题描述是“每个位置要盖 h[i] 层每次可以给一段连续区间整体加盖一层”那就是这道题。输入通常是这样5 2 3 4 1 2含义是有 5 个位置目标高度分别为 2、3、4、1、2。注意几个关键限制每次操作必须是连续区间每次只能 1目标高度可能很大但不会超过 int 范围比赛里一般 n 在 10^5 到 10^6 量级。这些限制决定了这题不能暴力如果真按题意模拟每次操作一个区间最坏情况复杂度是 O(高度和 × n)显然不行。先说答案再解释为什么。最少操作次数等于h[1] Σ max(0, h[i] - h[i-1]) i 从 2 到 n也就是从第一个位置开始每次遇到“高度上升”把上升的差值累加进答案高度下降或持平不加。用上面样例算一遍第 1 个位置h[1] 2答案先加 2当前 ans 2h[2]3 比 h[1]2 高 1ans 3h[3]4 比 h[2]3 高 1ans 4h[4]1 比 h[3]4 低不加ans 4h[5]2 比 h[4]1 高 1ans 5所以答案是 5。你可以手动模拟一下最少怎么 5 次完成第一次操作 [1,3] 整体 1第二次 [1,3] 整体 1第三次 [2,3] 整体 1第四次 [3,3] 整体 1第五次 [5,5] 整体 1。每次操作都是连续的最后高度变成 2、3、4、1、2。刚好 5 次。这个结论对第一次见的人来说可能有点反直觉为什么只累加“上升量”下降量不用管下面从两个角度拆开讲。2. 两个视角理解“正差分之和”贪心扫描与差分数组2.1 贪心扫描视角能续就续不能续就新开从左到右看相邻两个位置。假设当前已经处理到第 i-1 个位置它的高度 h[i-1] 已经由前面若干次操作覆盖到了。现在看第 i 个位置有两种情况如果 h[i] h[i-1]说明前一个位置的操作里有一部分“覆盖到 i-1 就结束”的操作可以顺手把右端点延长到 i让它们也把第 i 个位置盖到 h[i]。你不需要额外新开任何操作。当然前提是那些操作原本只覆盖到 i-1现在把右端点从 i-1 改到 i 即可区间连续性依然满足每个位置被覆盖的次数依然等于目标高度。如果 h[i] h[i-1]即使把前一个位置的所有操作都延伸到 i也只能把第 i 个位置盖到 h[i-1]还差 h[i] - h[i-1] 这么多层。这多出来的高度必须由新的操作来补齐。每次新操作最多给第 i 个位置加 1 层所以至少需要 h[i] - h[i-1] 次新操作。而且这些新操作可以都以 i 为左端点向右延伸覆盖需要加高的位置这样就能做到步数最少。把这两种情况合起来就是代码里那个 if 判断只有上升才累加差值。这就是贪心思想——每一步都在做局部最优决策并且可以证明局部最优能拼成全局最优。因为每个位置的“需求”从左到右依次满足新开的操作数恰好等于所有上升差之和任何方案都至少需要这么多操作。2.2 差分数组视角一次区间操作在差分数组上的表现第二种理解方式更硬核也更适合用来证明。构造差分数组 d[i] h[i] - h[i-1]其中定义 h[0] 0。拿样例 [2,3,4,1,2] 来说差分数组是d[1] 2 - 0 2 d[2] 3 - 2 1 d[3] 4 - 3 1 d[4] 1 - 4 -3 d[5] 2 - 1 1现在思考一次区间 [l, r] 整体 1 的操作在差分数组上会造成什么变化答案是 d[l] 增加 1d[r1] 减少 1。因为区间内部相邻位置的差值不变只有左端点位置的高度突然比前一个位置高 1以及右端点后面一个位置的高度突然比区间内低 1。如果 r n那么 d[n1] 不用管或者理解为存在一个 h[n1] 0d[n1] 相应减少 1。最终所有位置的高度达到 h等价于最终差分数组等于 d。而我们的操作本质上是把若干次“1/-1”的差分变化叠加起来。每一次操作都贡献一个 1 和一个 -1。最终差分数组里所有正数的总和就是所有操作中 1 贡献的总次数所有负数的绝对值总和就是所有操作中 -1 贡献的总次数。由于操作次数相同两者必须相等。因此最少操作次数 所有正差分之和 所有负差分绝对值之和。用样例验证正差分有 2、1、1、1和是 5负差分只有 -3绝对值是 3为什么不相等因为还有一个隐含的 d[6] h[6] - h[5] 0 - 2 -2 没算进去。把 h[n1]0 补上正差分和 5负差分绝对值 3 2 5完全相等。所以代码里只遍历到 n累加正差分就是答案。生活类比把差分数组里的正数想成“水龙头打开的次数”负数想成“水龙头关上的次数”。一次区间操作就相当于在一个位置开水龙头在另一个位置关水龙头。要制造出目标高度分布你至少得打开所有正数对应的水量所以答案就是正数和。这两种视角贪心扫描适合写代码时快速理解差分视角适合证明和给别人讲题。面试时如果时间充裕建议把差分视角讲出来面试官会觉得你不是只会背公式。3. 三种语言实现与关键细节解析题目本身不考察复杂数据结构就是单层循环 O(n)。但不同语言写起来有一些值得注意的坑尤其是数据类型和输入输出。3.1 Java 实现import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] h new int[n]; for (int i 0; i n; i) { h[i] sc.nextInt(); } long ans h[0]; // 第一个位置本身就是一次“上升”从0到h[0] for (int i 1; i n; i) { if (h[i] h[i - 1]) { ans h[i] - h[i - 1]; } } System.out.println(ans); } }几个细节答案变量用 long不要用 int。原因很简单最坏情况下 n 10^5每个 h[i] 10^5且高度单调递增答案大约是 n × 最大高度 10^10已经超出 int 范围。别在这个地方丢分。读入用 Scanner 虽然慢但 n 在 10^5 级别足够用。如果 n 达到 10^6建议换 BufferedReader 自己 split否则可能超时。循环从 i 1 开始因为 h[0] 已经单独初始化答案。也可以统一用差分写法ans 0然后判断 h[i] h[i-1]其中定义一个 h[n] 0循环 i 从 1 到 n。两种写法等价但第一种更直观。3.2 C 实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long h(n); for (int i 0; i n; i) { cin h[i]; } long long ans h[0]; for (int i 1; i n; i) { if (h[i] h[i - 1]) { ans h[i] - h[i - 1]; } } cout ans \n; return 0; }细节说明这里直接把 vector 声明成 long long是最保险的。如果你用 int 存 h[i]在 ans h[i] - h[i-1] 这一步差值本身不会超 int但累加会超所以至少 ans 要 long long。我习惯干脆全部 long long省得想。ios::sync_with_stdio(false); cin.tie(nullptr);是 C 输入输出加速标配不用白不用。不加速时 cin 在数据量大的情况下可能比 scanf 慢很多。如果题目要求多组测试数据记得每组循环前重置 ans。单组题没事但养成习惯。3.3 Python 实现def main(): n int(input()) h list(map(int, input().split())) ans h[0] for i in range(1, n): if h[i] h[i - 1]: ans h[i] - h[i - 1] print(ans) if __name__ __main__: main()细节说明Python 不需要担心整数溢出这点比 Java/C 省心。输入一行可能很长但 Python 的list(map(int, input().split()))足够处理 10^5 个整数。如果 n 达到 10^6建议用sys.stdin.buffer.read().split()一次性读入性能差异很大。还有一种更“Pythonic”的写法sum(max(0, h[i] - h[i-1]) for i in range(1, n)) h[0]。代码更短但可读性略差看个人习惯。笔试里推荐写清晰的版本万一出 bug 好排查。三种语言的时间复杂度完全一样O(n)空间复杂度是 O(n)主要花在存储 h 数组上。其实空间还可以优化到 O(1)因为只依赖前一个值用一个 pre 变量滚动即可。但笔试没必要存数组能让你调试时随时查看数据反而更稳。4. 在线测试与同类题目对照很多人刷题有个误区看完题解觉得自己会了不再验证。这题如果你只背公式很容易在边界输入上翻车。建议直接去 OJ 上提交用真实数据检验。4.1 两个可以直接用的 OJ 入口这题和洛谷 P1969【NOIP2013 提高组】积木大赛、P5019【NOIP2018 提高组】铺设道路是同一个模型题目描述几乎只是换了个背景。你可以把上面任意一份代码粘过去提交。P1969 积木大赛描述是“搭积木”n 个位置目标高度已知每次可以给一段连续区间 1求最少次数。P5019 铺设道路描述是“填坑”n 个路段目标深度已知每次可以给一段连续区间填 1 单位土求最少次数。这两个题数据范围和输入格式都与蚂蚁这道题基本一致非常适合当验证场。注意 P5019 的 n 范围可能更大用 C 记得开 long long。从这两个题也有一个有意思的发现同一个数学模型在不同年份、不同比赛的题目里反复出现。所以刷题不能只记题号要把“模型”抽出来。你一旦形成这种抽象能力遇到“搭房子”“修路”“填坑”“积木”这类换皮题都能秒杀。4.2 手写样例验证法如果你不方便上 OJ可以手写几个边界样例验证代码n 1h [5]。答案应该是 5。循环不进入ans h[0] 5正确。递增序列 h [1, 2, 3, 4]。答案应该是 4因为每次操作只需要从一个位置开始连续向右延伸4 次完成。公式1 (2-1) (3-2) (4-3) 4正确。递减序列 h [4, 3, 2, 1]。答案应该是 4。公式4 0 0 0 4。手动模拟第 1 个位置需要 4 次剩下位置都能沿用前一个位置的操作并提前结束所以总次数 4正确。全零数组 h [0, 0, 0]。答案应该是 0。公式0 0 0 0正确。锯齿序列 h [3, 1, 3, 1, 3]。公式3 0 2 0 2 7。可以自己画一下每座“山峰”都需要额外补差答案 7 是合理的。把这几组数据跑一遍代码逻辑基本可以放心。5. 常见问题与排查技巧实录这部分是我实际刷题过程中踩过或者看别人踩过的坑整理成清单希望能帮你少走弯路。5.1 问题题目看错把“区间 1”理解为“区间替换成目标值”这是最致命的错误。有些同学看到“盖房子”下意识认为每次操作是选一个区间直接盖到目标高度那答案就变成“有多少个不同高度连续段”了完全不是这道题。破局方法是先看样例把样例手工模拟一遍。如果模拟结果和公式答案一致说明理解对了不一致赶紧回头重读题。5.2 问题int 溢出高 n 单调递增的极限数据下答案可能达到 10^10 量级int 必炸。C/Java 选手务必使用 long long / long。这题数据弱一点可能 int 侥幸通过但笔试系统一旦用极限数据直接 WA。我的习惯是凡是累加类题目答案变量一律用 64 位不做任何侥幸。5.3 问题忘了第一个位置的“上升”从差分视角看h[0] 0所以 d[1] h[1] - 0 h[1] 是一个正差分必须算进答案。代码里体现在 ans 初始化为 h[0]。有人会写成 ans 0然后从 i 0 开始判断 h[i] h[i-1]但 i 0 时 h[i-1] 越界处理起来更麻烦。用 ans h[0] 配合从 1 遍历是最干净的写法。5.4 问题多组输入没有重置数据某些 OJ 的题目会以多组测试用例的形式给出每组以 n 开头直到读到 EOF。如果你在一个 while 循环里读一定记得每组开始时重新初始化 ans或者让 ans 在循环内部声明。Java 里把long ans声明在 while 内部即可C 同理。5.5 问题Python 读入慢导致超时n 10^6 时input().split()可能 TLE。建议用sys.stdin.buffer.read().split()一次性读入然后逐个转 int。代码示例import sys data list(map(int, sys.stdin.buffer.read().split())) n data[0] h data[1:] ans h[0] for i in range(1, n): if h[i] h[i - 1]: ans h[i] - h[i - 1] print(ans)注意这样写的前提是输入格式正确第一个数是 n后面恰好跟 n 个整数。如果数据里有多余空格或换行这种方法依然能正确处理因为 split 会把所有空白字符都忽略。5.6 问题被“最少”两个字带偏去设计复杂算法有人看到“最少”就想 DP 或者二分其实这题根本没有子问题重叠一个线性扫描就结束了。这类题的精髓恰恰是“看似需要规划实际贪心即可”。建议拿到题先画一画高度柱状图观察相邻柱子的变化再决定用什么算法。如果画完图发现“只有上升才需要新操作”那就不用想别的方法了。6. 进阶思考从这题延伸出去的知识点这道题虽然只是春招第一题但它背后牵扯出的模型非常值得展开。6.1 与差分数组的关系差分数组本身是区间操作题目的基础工具。你学完这题应该形成一个条件反射见到“区间整体加减某个值”立刻想到转换成差分数组上的两个单点修改。这在后续刷区间修改区间查询的题目时非常有用。比如 LeetCode 上的拼车、航班预订统计几乎就是差分数组的裸题。从差分视角还能得出一个结论最少操作次数等于差分数组中所有正数之和也等于所有负数绝对值之和。这给了你一个验证答案正确性的方法算出来答案后把差分数组所有正数加起来再算所有负数绝对值加起来两者应该相等。如果不相等说明你漏了末尾的 h[n1] 0 这个隐含位置。6.2 相似题型的举一反三这类“最少区间操作达到目标数组”的题目还有一个常见变种每次操作可以选择一个连续区间整体 1 或整体 -1求最少操作次数。这个变种的答案变成了“所有相邻高度差的绝对值之和的一半”不对其实答案是正差分之和加上负差分绝对值之和再除以 2我可以告诉你并不等于简单分半。更严谨地说如果允许 1 和 -1 都可以那么最优解可以用正差分之和因为你可以用 -1 操作消掉负差分本质依然是差分数组正数总和。所以这题的解法适用面很广。还有一个变种是“每次操作可以选择一个区间变成任意值”那就是另一个贪心问题了。思路不同注意区分。6.3 把“搭房子”讲给面试官如果面试官让你解释思路一个简洁的表达方式是把目标高度画成柱状图从左往右看。每根柱子的高度如果比左边高就必须“额外”增加那么多次操作因为左边的操作已经覆盖不到这里多出的部分如果比左边低则可以直接沿用左边的操作并提前结束。所以答案累计所有上升差。这个表达既解释了贪心策略也蕴含了操作构造过程。如果再补一句“等价于差分数组的正数和”面试官通常会点头。7. 最后再分享一个小技巧我刷这类题有个习惯拿到题目先不急着写代码而是手动画柱状图模拟一遍样例。模拟的过程中你会天然发现“下降不用管上升要累加”的规律。一旦规律浮出水面代码就是顺手的事。另外笔试时第一题通常是热身题不要因为慌张直接套模板花 30 秒把样例算明白比多写 50 行代码有用得多。如果你今年也在准备蚂蚁或者其他大厂的春招建议把这题和 P1969/P5019 放在同一天刷完然后试着用自己的话把“差分数组视角”讲给别人听。能讲明白才是真会了。祝笔试顺利。