Easy

题目描述

有一个骑手要去进行一次公路旅行。这次旅行包含 n + 1 个不同海拔的点。骑手从海拔为 0 的点 0 开始旅行。

给你一个长度为 n 的整数数组 gain，其中 gain[i] 是点 i 和点 i + 1 的净海拔增长值（对于所有 0 <= i < n）。请你返回最高点的海拔。

示例 1：

输入：gain = [-5,1,5,0,-7]
输出：1
解释：海拔高度为 [0,-5,-4,1,1,-6]。最高海拔为 1。

示例 2：

输入：gain = [-4,-3,-2,-1,4,3,2]
输出：0
解释：海拔高度为 [0,-4,-7,-9,-10,-6,-3,-1]。最高海拔为 0。

约束条件：

  • n == gain.length
  • 1 <= n <= 100
  • -100 <= gain[i] <= 100

提示：

  • 注意某个元素的海拔是其前面所有元素增益的总和
  • 获得海拔可以通过获得给定数组的前缀和数组来完成

解题思路

这是一道典型的前缀和问题。我们需要理解题目的核心：骑手从海拔 0 开始，每次移动的海拔变化由 gain 数组给出，我们需要找到整个行程中的最高海拔。

解法一：直接模拟（推荐） 最直观的方法是模拟整个过程。我们维护当前海拔和最高海拔两个变量。从起点开始，逐个累加 gain 数组中的值，每次更新当前海拔后，都检查是否超过了历史最高海拔。

解法二：前缀和数组 我们也可以先构建完整的海拔数组，然后找出最大值。但这需要额外的空间，不如解法一优雅。

由于题目规模较小（n ≤ 100），两种方法的性能差异可以忽略，但解法一在空间复杂度上更优，且代码更简洁。

关键点是理解海拔的计算：每个点的海拔 = 起始海拔（0）+ 到达该点的所有增益之和。

代码实现

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int currentAltitude = 0;
        int maxAltitude = 0;
        
        for (int g : gain) {
            currentAltitude += g;
            maxAltitude = max(maxAltitude, currentAltitude);
        }
        
        return maxAltitude;
    }
};

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        current_altitude = 0
        max_altitude = 0
        
        for g in gain:
            current_altitude += g
            max_altitude = max(max_altitude, current_altitude)
        
        return max_altitude

public class Solution {
    public int LargestAltitude(int[] gain) {
        int currentAltitude = 0;
        int maxAltitude = 0;
        
        foreach (int g in gain) {
            currentAltitude += g;
            maxAltitude = Math.Max(maxAltitude, currentAltitude);
        }
        
        return maxAltitude;
    }
}

var largestAltitude = function(gain) {
    let currentAltitude = 0;
    let maxAltitude = 0;
    
    for (let g of gain) {
        currentAltitude += g;
        maxAltitude = Math.max(maxAltitude, currentAltitude);
    }
    
    return maxAltitude;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

分析：

  • 时间复杂度：O(n)，需要遍历一次 gain 数组
  • 空间复杂度：O(1)，只使用了常数个额外变量