力扣链接：1732. 找到最高海拔，难度等级：简单。
有一个自行车手打算进行一场公路骑行，这条路线总共由 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
提示 1
Let's note that the altitude of an element is the sum of gains of all the elements behind it
提示 2
Getting the altitudes can be done by getting the prefix sum array of the given array
思路
题目要求找到公路骑行过程中达到的最高海拔。自行车手从海拔 0 开始。gain 数组表示连续两点之间的海拔变化。
这意味着在任意点 i 的海拔是直到点 i-1 的所有海拔变化的总和（即前缀和）。我们可以维护一个累加的当前海拔高度，并不断更新遇到的最高海拔。
👋 站长寄语：我还为你开发了 coder.id - 打造程序员个人IP， 包含作品集、简历和博客等，助您顺利拿到 Offer！
步骤
- 初始化两个变量：
current_altitude（当前海拔）设为0，max_altitude（最高海拔）设为0。 - 遍历
gain数组中的每一个海拔变化值g。 - 将
g加到current_altitude上，得到下一个点的实际海拔。 - 比较
max_altitude和current_altitude，将两者中的较大值赋给max_altitude。 - 遍历结束后，返回
max_altitude即可。
复杂度
时间复杂度
O(N)
空间复杂度
O(1)
解释
- 时间复杂度:
O(N)，其中N是数组gain的长度。我们只需要对数组进行一次遍历。 - 空间复杂度:
O(1)。我们仅仅使用了几个整型变量来存储当前海拔和最高海拔，因此需要的额外空间是常数级别的。
Python #
class Solution:
def largestAltitude(self, gain: List[int]) -> int:
current_altitude = 0
max_altitude = 0
for g in gain:
current_altitude += g
if current_altitude > max_altitude:
max_altitude = current_altitude
return max_altitude
Java #
class Solution {
public int largestAltitude(int[] gain) {
int currentAltitude = 0;
int maxAltitude = 0;
for (int g : gain) {
currentAltitude += g;
if (currentAltitude > maxAltitude) {
maxAltitude = currentAltitude;
}
}
return maxAltitude;
}
}
JavaScript #
/**
* @param {number[]} gain
* @return {number}
*/
var largestAltitude = function(gain) {
let currentAltitude = 0;
let maxAltitude = 0;
for (const g of gain) {
currentAltitude += g;
if (currentAltitude > maxAltitude) {
maxAltitude = currentAltitude;
}
}
return maxAltitude;
};
Cpp #
class Solution {
public:
int largestAltitude(vector<int>& gain) {
int currentAltitude = 0;
int maxAltitude = 0;
for (int g : gain) {
currentAltitude += g;
if (currentAltitude > maxAltitude) {
maxAltitude = currentAltitude;
}
}
return maxAltitude;
}
};
Csharp #
public class Solution {
public int LargestAltitude(int[] gain) {
int currentAltitude = 0;
int maxAltitude = 0;
foreach (int g in gain) {
currentAltitude += g;
if (currentAltitude > maxAltitude) {
maxAltitude = currentAltitude;
}
}
return maxAltitude;
}
}
Go #
func largestAltitude(gain []int) int {
currentAltitude := 0
maxAltitude := 0
for _, g := range gain {
currentAltitude += g
if currentAltitude > maxAltitude {
maxAltitude = currentAltitude
}
}
return maxAltitude
}
Ruby #
# @param {Integer[]} gain
# @return {Integer}
def largest_altitude(gain)
current_altitude = 0
max_altitude = 0
gain.each do |g|
current_altitude += g
max_altitude = current_altitude if current_altitude > max_altitude
end
max_altitude
end
Rust #
impl Solution {
pub fn largest_altitude(gain: Vec<i32>) -> i32 {
let mut current_altitude = 0;
let mut max_altitude = 0;
for g in gain {
current_altitude += g;
if current_altitude > max_altitude {
max_altitude = current_altitude;
}
}
max_altitude
}
}
Kotlin #
class Solution {
fun largestAltitude(gain: IntArray): Int {
var currentAltitude = 0
var maxAltitude = 0
for (g in gain) {
currentAltitude += g
if (currentAltitude > maxAltitude) {
maxAltitude = currentAltitude
}
}
return maxAltitude
}
}
Swift #
class Solution {
func largestAltitude(_ gain: [Int]) -> Int {
var currentAltitude = 0
var maxAltitude = 0
for g in gain {
currentAltitude += g
if currentAltitude > maxAltitude {
maxAltitude = currentAltitude
}
}
return maxAltitude
}
}
其它语言
欢迎贡献代码到 GitHub repo -> 1732. 找到最高海拔。感谢！打造你的开发者个人IP
- 📄 简历 + 作品集 + 博客
- 🌐 支持绑定自定义域名
- ✨ 顶级子域名：
https://yourname.coder.id