LeetCode 1732. 找到最高海拔
题目描述
题意分析
路线起点海拔为零，
gain[i]表示从第i个地点到第i + 1个地点的海拔变化。正数表示上升，负数表示下降，零表示海拔不变，求整条路线到达过的最高海拔。输入给的是相邻地点的差值，不是各地点本身的海拔，也不是只求某段爬升的最大增量。
n段变化对应n + 1个地点，起点同样需要参与最高值比较。
解法：滚动前缀和记录最高点
核心思路
[!blue]
当前海拔由前一个地点的海拔加本段变化得到。从零出发，走过前若干段后的海拔，就是这些
gain的前缀和，因此按输入顺序累加即可还原每个地点的海拔。用
cur保存当前地点的海拔，用ans保存此前到达过的最高值。每读取一段变化，先执行cur += g到达下一个地点，再用新的cur更新最大值。处理完前i段后，cur对应第i个地点，ans已覆盖从起点到这里的全部地点。两个变量都初始化为零：
cur表示还没出发，ans则把起点纳入候选。如果之后所有地点都低于起点，答案仍然正确保留为零。下降路段不能忽略，也不能把负海拔重置为零，因为后面的每次上升都以真实的当前海拔为基础。只需要最高值，不需要输出各地点海拔，所以前缀和可以滚动保存在一个变量中，无须创建完整前缀数组。
解题步骤
- 将当前海拔
cur和最高海拔ans都设为零。- 按顺序读取每段变化，先加到
cur，恢复下一个地点的海拔。- 将
ans更新为原最高值与当前海拔中的较大者。- 所有路段处理完后返回
ans。
代码实现
class Solution {
public int largestAltitude(int[] gain) {
// 答案初值即起点海拔 0，因为起点也是到达过的位置
int ans = 0;
// 当前海拔，滚动保存 gain 的前缀和
int cur = 0;
for (int g : gain) {
// 累加净变化，推进到下一个位置的海拔
cur += g;
// 累加之后再比较，保证每个位置都被纳入
ans = Math.max(ans, cur);
}
return ans;
}
}
func largestAltitude(gain []int) int {
// ans 初值即起点海拔 0；cur 滚动保存 gain 的前缀和
ans, cur := 0, 0
for _, g := range gain {
// 累加净变化，推进到下一个位置的海拔
cur += g
if cur > ans {
// 累加之后再比较，保证每个位置都被纳入
ans = cur
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，每段海拔变化读取一次，每次只做一次累加和比较。
- 空间复杂度：$O(1)$，仅保存当前海拔和历史最大值，不修改输入。
关键点总结
[!green]
- 地点海拔是从起点开始的前缀和，单段变化本身不代表所在高度。
- 初始答案零负责计入第一个地点，后续每轮负责计入一个新地点。
- 当前值与历史最大值职责不同，只保留最大值无法继续还原下一地点。
易错点总结
[!yellow]
- 把最大的
gain当成最高海拔，忽略了此前路段的累计影响。- 只累加上升路段或把负海拔归零，会改变真实路线高度。
- 遗漏起点，整条路线低于零时就会错误返回负数。
- 在累加本段变化前才比较，若循环结束不再更新，会漏掉最终地点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1480. 一维数组的动态和 | 简单 | 同样通过前缀累加恢复每个位置的累计值，本题只取最大值所以无需保存整个结果数组。 |
| 303. 区域和检索 - 数组不可变 | 简单 | 同样利用前缀和表示累计量，原题保留数组供多次区间查询，本题一遍扫描即可。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！