题目描述

有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。给你一个长度为 n 的整数数组 gain，其中 gain[i] 是点 i 和点 i + 1 的净海拔高度差（0 <= i < n）。请你返回最高点的海拔。

例如：gain = [-5,1,5,0,-7]，输出 1。

解释：海拔变化：0 → -5 → -4 → 1 → 1 → -6，最高海拔为 1。

解题思路

核心思想

这是一个典型的前缀和问题。给定相邻两点之间的高度差数组 gain，我们需要求出所有点的海拔值中的最大值。

设点 0 的海拔 altitude[0] = 0，则：

  • altitude[1] = altitude[0] + gain[0]
  • altitude[2] = altitude[1] + gain[1]
  • …
  • altitude[i+1] = altitude[i] + gain[i]

每个点的海拔都是前一个点的海拔加上对应的高度差，这正是前缀和。

步骤

  1. 创建一个长度为 n+1 的数组 prefixAndGain，其中 prefixAndGain[0] = 0。
  2. 遍历 gain，计算每个点的海拔：prefixAndGain[i+1] = prefixAndGain[i] + gain[i]。
  3. 遍历 prefixAndGain，记录最大值并返回。

空间优化

实际上不需要存储所有前缀和：

  • 维护一个变量 currentAltitude，初始为 0。
  • 维护 maxAltitude，初始为 0（因为起点海拔为 0）。
  • 每步更新 currentAltitude += gain[i]，然后更新 maxAltitude = max(maxAltitude, currentAltitude)。

示例说明

以 gain = [-5,1,5,0,-7] 为例：

  • 起点海拔 = 0，max = 0
  • gain[0] = -5 → 海拔 = -5，max = 0
  • gain[1] = 1 → 海拔 = -4，max = 0
  • gain[2] = 5 → 海拔 = 1，max = 1
  • gain[3] = 0 → 海拔 = 1，max = 1
  • gain[4] = -7 → 海拔 = -6，max = 1
  • 返回 1

复杂度分析

  • 时间复杂度：O(n)，一次遍历即可。
  • 空间复杂度：O(n)（代码中使用前缀数组）或 O(1)（优化后仅使用变量）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
package code.J1732;

public class J1732 {
    public int largestAltitude(int[] gain) {
        int[] prefixAndGain = new int[gain.length + 1];
        for (int i = 0; i < gain.length; i++) {
            prefixAndGain[i + 1] = prefixAndGain[i] + gain[i];
        }
        int max = Integer.MIN_VALUE;
        for (int j : prefixAndGain) max = Math.max(max, j);
        return max;
    }
}