LeetCode 1732. 找到最高海拔

2026-07-14 HGNULB 约 9 分钟

文章信息 3 个分类 2 个标签

分类

题目描述

✅ 1732. 找到最高海拔

题意分析

骑行者从海拔 0 出发，一共走 n 段路。要求返回整段旅途中到达过的最高海拔。

第一个关键点：gain[i] 给的不是海拔，而是第 i 段路的净海拔变化（增量）。所以「海拔」这个量在输入里根本没有直接给出，需要自己累出来：走完第 i 段路后所处的海拔，等于 gain[0] + gain[1] + … + gain[i]，也就是 gain 的前 i + 1 项之和。整条旅途一共经过 n + 1 个位置，对应的海拔序列是 0, gain[0], gain[0] + gain[1], …，即「一个 0 打头，后面接 gain 的各阶前缀和」。

第二个关键点：起点的海拔 0 本身也是候选答案。题目问的是「到达过的最高海拔」，起点是到达过的位置之一。如果全程一路向下，那么所有后续海拔都是负数，最高点就是出发那一刻。官方第二个样例 gain = [-4, -3, -2, -1, 4, 3, 2] 正是这种情况：海拔序列为 [0, -4, -7, -9, -10, -6, -3, -1]，答案 0 就是起点，一个从未在 gain 里出现的值。

约束透露的信号：1 <= n <= 100，-100 <= gain[i] <= 100。数据规模极小，说明本题考的不是效率而是建模是否正确；同时海拔的取值范围被夹在 [-10000, 10000] 内，int 完全够用，不必担心溢出，也不必上 long。

边界：n = 1 时只有一段路，答案是 max(0, gain[0])——上升就返回 gain[0]，下降就返回起点 0；题目保证 n >= 1，不存在空数组。

解法：前缀和边扫边取最大

核心思路

把「增量序列」转成「海拔序列」，这道题就退化成一个再简单不过的问题：求一个序列的最大值。

转换规则就是前缀和：设 $S_k = \sum_{i=0}^{k-1} gain[i]$，则 $S_0 = 0$（起点），$S_1, S_2, …, S_n$ 依次是走完每一段路后的海拔。要求的答案就是 $\max(S_0, S_1, …, S_n)$。注意最大值是在包含 $S_0$ 的 $n + 1$ 个数里取，这正是「起点 0 必须参与比较」的数学表述。

为什么不需要显式建一个前缀和数组？因为 $S_k = S_{k-1} + gain[k-1]$，每个前缀和只依赖它的前一个。求最大值也只需要顺序看一遍每个元素，不需要回头访问任何历史值。既然「生成」和「消费」都是严格从左到右且一次性的，就没必要把中间结果存下来——用一个变量滚动保存当前前缀和，再用一个变量保存已见过的最大值，空间从 $O(n)$ 压到 $O(1)$。

不变量：循环处理完 gain[0..i] 后，cur 恰好等于 $S_{i+1}$（即走完第 i 段路后的海拔），ans 恰好等于 $\max(S_0, S_1, …, S_{i+1})$。循环开始前 i = -1，此时 cur 与 ans 都等于 $S_0 = 0$，不变量成立；每轮先 cur += gain[i] 把 cur 推进到下一个前缀和，再 ans = max(ans, cur) 把新出现的候选纳入比较，不变量得以保持。循环结束时 i = n - 1，ans 就是 $\max(S_0, …, S_n)$，正是答案。

这也解释了为什么答案变量的初值必须是 0 而不是 Integer.MIN_VALUE：ans 的语义是「到目前为止见过的最高海拔」，而在一步都没走之前，已经见过的海拔恰好是起点的 0。初值取 0 不是什么特殊处理或打补丁，而是不变量在 i = -1 时的自然取值。

解题步骤

初始化 cur = 0，表示当前海拔。为什么是 0：题目规定骑行者从海拔 0 出发，cur 代表的是「空前缀之和」。

初始化 ans = 0，表示答案。为什么是 0 而不是极小值：起点是到达过的位置，它的海拔 0 天然是一个候选答案；若初值取极小值，全程下降的用例会返回负数。

从左到右遍历 gain，每拿到一个增量 g 就执行 cur += g。为什么：这一步把 cur 从「上一个位置的海拔」推进到「下一个位置的海拔」，用的是前缀和的递推关系。

紧接着执行 ans = max(ans, cur)。为什么必须在累加之后比较：cur 更新后才是一个真实到达过的新海拔；若先比较再累加，最后一个位置的海拔就永远进不了比较。

遍历结束返回 ans。为什么正确：n + 1 个位置的海拔各被比较过恰好一次（起点由初值代表，其余 n 个由循环覆盖），无遗漏无重复。

以 gain = [-5, 1, 5, 0, -7] 走一遍：

出发前：cur = 0，ans = 0。

读 gain[0] = -5：cur = 0 + (-5) = -5；-5 < 0，ans 仍为 0。

读 gain[1] = 1：cur = -5 + 1 = -4；-4 < 0，ans 仍为 0。

读 gain[2] = 5：cur = -4 + 5 = 1；1 > 0，ans 更新为 1。

读 gain[3] = 0：cur = 1 + 0 = 1；1 不大于 1，ans 仍为 1。

读 gain[4] = -7：cur = 1 + (-7) = -6；-6 < 1，ans 仍为 1。

返回 ans = 1。完整海拔序列为 [0, -5, -4, 1, 1, -6]，最大值确为 1，与官方样例一致。

再以 gain = [-4, -3, -2, -1, 4, 3, 2] 走一遍：cur 依次为 -4, -7, -9, -10, -6, -3, -1，全程为负，没有任何一次能超过初值。虽然后半段连续上升了 4 + 3 + 2 = 9，但前半段先掉了 10，爬回来还差一点，终点海拔 -1 仍低于出发点。因此 ans 从头到尾保持初值 0，答案就是起点的海拔。这个样例的价值在于：答案根本不在 gain 的任何前缀和里，只存在于初值中——它专门用来打死「初值取极小值」和「初值取 gain[0]」这两种写法。

代码实现

class Solution {
    public int largestAltitude(int[] gain) {
        int ans = 0; // 答案初值即起点海拔 0，因为起点也是到达过的位置
        int cur = 0; // 当前海拔，滚动保存 gain 的前缀和
        for (int g : gain) {
            cur += g;                     // 累加净变化，推进到下一个位置的海拔
            ans = Math.max(ans, cur);     // 累加之后再比较，保证每个位置都被纳入
        }

        return ans;
    }
}

func largestAltitude(gain []int) int {
    ans, cur := 0, 0 // ans 初值即起点海拔 0；cur 滚动保存 gain 的前缀和
    for _, g := range gain {
        cur += g // 累加净变化，推进到下一个位置的海拔
        if cur > ans {
            ans = cur // 累加之后再比较，保证每个位置都被纳入
        }
    }

    return ans
}

复杂度分析

时间复杂度：$O(n)$，其中 n 为 gain 的长度。每个增量只被读取一次，循环内只有一次加法和一次比较，都是常数时间。

空间复杂度：$O(1)$，只用了 ans 和 cur 两个整数变量，没有开与输入规模相关的数组。

关键点总结

题目给的是增量，就要想到前缀和。凡是输入描述为「变化量」「差值」「每步的收益」而问题问的是「某个位置的实际值」，两者之间的桥梁就是前缀和。识别出这一层，题目往往当场退化成一个基础问题——本题退化成了「求序列最大值」。

答案的候选集合里包含初始状态时，答案变量的初值必须取初始状态的值，而不是 Integer.MIN_VALUE。起点海拔 0 是一个合法的到达点，把它写进初值，相当于在循环开始前就完成了对它的比较；反过来说，只有当初始状态不是候选答案时才该用极小值兜底。这条判断永远从题意出发，不能靠习惯。

前缀和的生成与消费都是单向一次性时，不要建数组。判据是：递推只依赖前一项，且后续不再回头访问历史前缀和。满足这两条就可以把数组塌缩成一个滚动变量。反例是 303、560 这类需要回查任意历史前缀的题，那才真的需要数组或哈希表。

累加与比较的先后顺序要和不变量对齐。本题必须「先累加、后比较」，因为只有更新后的 cur 才对应一个真实到达过的位置；顺序写反会漏掉终点。写循环前先把不变量写清楚，顺序问题自然就定了。

面试视角：这题面试官期望你直接给出 $O(1)$ 空间的滚动写法。如果你先建一个长度为 n + 1 的前缀和数组再求最大值，功能上没错，但几乎必然被追问「空间还能优化吗」——因为数组里的每个值都只用了一次，冗余存储一眼可见。一上手就滚动变量，既省掉一轮来回，也表明你理解了「前缀和是一种递推关系，不必然是一个数组」。

小数据规模的 easy 题，考点在建模而非优化。n <= 100 意味着任何做法都能过，此时代码要拼的是边界是否严谨（起点是否算、初值是否对）而不是常数是否小。

易错点总结

答案初值取 Integer.MIN_VALUE，只在累加后比较，起点 0 从未参与：用全负用例 gain = [-1, -2, -3] → 返回 -1，期望 0；用官方第二个样例 gain = [-4, -3, -2, -1, 4, 3, 2] → 返回 -1，期望 0。根因是漏掉了「起点也是到达过的位置」这个候选。

答案初值取 gain[0]：gain = [-4, -3, -2, -1, 4, 3, 2] → 返回 -1，期望 0。更危险的是这种写法在官方第一个样例 gain = [-5, 1, 5, 0, -7] 上恰好返回 1（正确），只跑第一个样例会误以为通过。gain[0] 是「第一段路的增量」，把它当海拔的初值属于概念混用。

把 gain[i] 当成海拔直接取最大值：gain = [-5, 1, 5, 0, -7] → 返回 5，期望 1；gain = [-4, -3, -2, -1, 4, 3, 2] → 返回 4，期望 0。这是彻底没做增量到海拔的转换，直接把输入当结果。

先比较再累加（ans = max(ans, cur) 写在 cur += g 之前）：gain = [1, 2, 3] → 返回 3，期望 6，终点海拔被漏掉。同样有欺骗性——它在官方第一个样例上恰好返回 1（正确），因为该样例的最高点不在终点。

循环从 i = 1 开始，误以为 gain[0] 就是起点海拔：gain = [-5, 1, 5, 0, -7] → 返回 6，期望 1；gain = [1, 2, 3] → 返回 5，期望 6。整条海拔序列被整体平移，gain[0] 这一段路凭空消失了。

只比较终点海拔，即累加完全部 gain 后返回 max(0, cur)：gain = [-5, 1, 5, 0, -7] → 返回 0，期望 1。题目问的是「途中到达过的最高海拔」而不是「终点海拔」，中间的峰值必须逐个比较。

对前缀和取绝对值后比较（把「最高」误解为「离海平面最远」）：gain = [-5, 1, 5, 0, -7] → 返回 6，期望 1。-6 的绝对值最大，但它是全程最低点，不是最高点。

写成 ans = max(ans, cur + g) 却忘记更新 cur：gain = [-5, 1, 5, 0, -7] → 返回 5，期望 1。cur 恒为 0，实际退化成了「取 gain 的最大值」，和第三条殊途同归。

Go 里把变量命名为 max 之后又调用内置 max 函数：直接编译失败，报 invalid operation: cannot call max (variable of type int): int is not a function。Go 1.21 起 max 是内置函数，被同名局部变量遮蔽后就不能再当函数用了，改名为 ans 或改用 if cur > ans 即可。

相似题目

题目	难度	考察点
1480. 一维数组的动态和	简单	要求返回整个前缀和序列而非其最大值，前缀和是输出本身，因此必须落地成数组（可原地改写），无法滚动成一个变量
724. 寻找数组的中心下标	简单	同样一遍扫描滚动前缀和，但比较对象是「左侧和」与「总和减左侧和」，需要先求一次总和，是双向前缀的对比而非单向取最值
303. 区域和检索 - 数组不可变	简单	需要多次回查任意区间，历史前缀和会被反复访问，正是本题「不必建数组」判据的反例，必须预处理成前缀和数组换 $O(1)$ 查询
53. 最大子数组和	中等	求的是前缀和之差的最大值（最大区间和）而非前缀和本身的最大值，需要额外维护历史最小前缀和，滚动变量从一个变成两个