1732. 找到最高海拔
1732. 找到最高海拔
题目
There is a biker going on a road trip. The road trip consists of n + 1
points at different altitudes. The biker starts his trip on point 0
with altitude equal 0
.
You are given an integer array gain
of length n
where gain[i]
is the net gain in altitude between points i
and i + 1
for all (0 <= i < n
). Return thehighest altitude of a point.
Example 1:
Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.
Example 2:
Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.
Constraints:
n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100
题目大意
有一个自行车手打算进行一场公路骑行,这条路线总共由 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
解题思路
可以通过遍历 gain
数组来计算每个点的海拔高度,记录最高的海拔值。
- 初始化:设置
max
为 0(起始海拔)和altitude
为 0。 - 遍历
gain
数组:- 对于每个海拔变化
h
,更新当前海拔altitude
。 - 更新最高海拔
max
为当前海拔与之前最高海拔的最大值。
- 对于每个海拔变化
- 返回结果:遍历结束后,返回最高海拔
max
。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是数组的长度,需要遍历数组。 - 空间复杂度:
O(1)
,使用了常数个变量。
代码
/**
* @param {number[]} gain
* @return {number}
*/
var largestAltitude = function (gain) {
// 记录最高海拔,初始化为 0
let max = 0;
// 初始海拔为 0
let altitude = 0;
for (let h of gain) {
// 计算当前海拔
altitude += h;
// 更新最高海拔
max = Math.max(max, altitude);
}
// 返回最高海拔
return max;
};