1732-找到最高海拔

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

有一个自行车手打算进行一场公路骑行，这条路线总共由 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 的海拔高度为 0，点 i~(i > 0) 的海拔高度为：

\sum_{k=0}^{i-1} \textit{gain}[i]

因此，我们只需要对数组 gain 进行一次遍历，在遍历到第 i 个元素时，使用前缀和的思想维护前 i 个元素的和，并用和更新答案即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int ans = 0, sum = 0;
        for (int x: gain) {
            sum += x;
            ans = max(ans, sum);
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int largestAltitude(int[] gain) {
        int ans = 0, sum = 0;
        for (int x : gain) {
            sum += x;
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int LargestAltitude(int[] gain) {
        int ans = 0, sum = 0;
        foreach (int x in gain) {
            sum += x;
            ans = Math.Max(ans, sum);
        }
        return ans;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        ans = total = 0
        for x in gain:
            total += x
            ans = max(ans, total)
        return ans
[sol1-C]
1
2
3
4
5
6
7
8
9
10
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int largestAltitude(int* gain, int gainSize){
     int ans = 0, sum = 0;
    for (int i = 0; i < gainSize; i++) {
        sum += gain[i];
        ans = MAX(ans, sum);
    }
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
var largestAltitude = function(gain) {
    let ans = 0, sum = 0;
    for (const x of gain) {
        sum += x;
        ans = Math.max(ans, sum);
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func largestAltitude(gain []int) (ans int) {
    total := 0
    for _, x := range gain {
        total += x
        ans = max(ans, total)
    }
    return
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

复杂度分析

  • 时间复杂度：O(n)。

  • 空间复杂度：O(1)。

 Comments
On this page
1732-找到最高海拔