难度: 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.length1 <= n <= 100-100 <= gain[i] <= 100运行时间: 20 ms
内存: 16.0 MB
class Solution:
def largestAltitude(self, gain: List[int]) -> int:
cur_height = max_height = 0
for g in gain:
cur_height += g
max_height = max(max_height, cur_height)
return max_height
这道题目通过计算从起点出发到每个点的海拔高度，然后找出最高的海拔。首先，初始化当前海拔（cur_height）为0，这是起始点的海拔。同时，用一个变量（max_height）来跟踪遇到的最高海拔，也初始化为0。然后，遍历数组 gain，每次通过累加 gain[i] 来更新当前海拔，每次更新后，比较并可能更新最高海拔。这样，遍历完成后，max_height 将包含最大海拔值。
时间复杂度: O(n)
空间复杂度: O(1)
# 定义解决方案类
class Solution:
def largestAltitude(self, gain: List[int]) -> int:
# 初始化当前海拔和最高海拔都为0
cur_height = max_height = 0
# 遍历每个高度差
for g in gain:
# 更新当前海拔
cur_height += g
# 更新最高海拔
max_height = max(max_height, cur_height)
# 返回计算得到的最高海拔
return max_height
在代码中，`cur_height`表示从起点开始到当前点的累积海拔高度。由于起点的海拔是0，因此`cur_height`初始化为0。同时，`max_height`用于记录遍历过程中遇到的最高海拔。初始化为0是因为考虑到即使所有的`gain`值都小于0，起点的海拔（即0）可能仍然是最高点。这样设置可以确保即使所有增益都是负的，算法仍能返回正确的最高海拔，即0。
代码通过一个循环遍历`gain`数组，每次循环中通过`cur_height += g`更新当前海拔。这一操作确保了在每一步都加上了从上一点到当前点的海拔变化。接着，使用`max_height = max(max_height, cur_height)`确保在每步之后，`max_height`都是之前所有点中的最高值。这样，无论何时，`max_height`都是到目前为止遇到的最高海拔。
如果`gain`数组中所有值都是负数，那么`cur_height`将在每次迭代后递减。然而，由于`max_height`初始化为0，即使所有的`gain`都是负数，`max_height`在第一次比较时（即在遍历`gain`之前）就已经设为了起点的海拔0。因此，即使`cur_height`的值持续下降，`max_height`会保持为0，这是正确的最高海拔值。
这种算法的时间复杂度为O(n)，其中n是`gain`数组的长度。因此，该算法能有效地处理非常大的n值，只要机器的内存足以存储输入数组。对于非常小的n值，例如n为0或1，算法同样有效。在n为0的情况下，由于没有任何增益，最高海拔将保持在初始化的0。总的来说，这种算法适用于所有规模的输入。