侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【前缀和】找到最高海拔

GabrielxD
2022-11-19 / 0 评论 / 0 点赞 / 18 阅读 / 374 字 / 正在检测是否收录...

题目

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.length
  • 1 <= n <= 100
  • -100 <= gain[i] <= 100

解题

方法一:前缀和

思路

根据题目描述,点 00 的海拔高度为 00,点 i(i>0)i(i > 0) 的海拔高度为:

j=0i1gain[j]\sum_{j=0}^{i-1}gain[j]

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

代码

class Solution {
    public int largestAltitude(int[] gain) {
        int prev = 0, max = 0;
        for (int g : gain) {
            max = Math.max(max, g + prev);
            prev += g;
        }
        return max;
    }
}
0

评论区