找到最高海拔【LC1732】

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 the highest altitude of a point.

有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。

给你一个长度为 n 的整数数组 gain ，其中 gain[i] 是点 i 和点 i + 1 的 净海拔高度差（0 <= i < n）。请你返回 最高点的海拔 。

美好的一天从leetcode开始

• 思路：遍历数组，使用前缀和求每一个点的海拔高度，取最大值返回既可

• 实现

class Solution {
    public int largestAltitude(int[] gain) {
        int res = 0;
        int height = 0;
        for (int i = 0; i < gain.length; i++){
            height += gain[i];
            res = Math.max(res,height);
        }
        return res;
    }
}

• 复杂度

。时间复杂度：O ( n ) ，n为数组长度

。空间复杂度：O ( 1 )