力扣(LeetCode)1732. 找到最高海拔(C++)

前缀和

这道题，很容易看出，$gain$ (海拔高度差) 是海拔高度的一个差分，对 $gain$ 用前缀和，就能求出每个点的海拔了。题目要求我们，找最高海拔，那么只需要维护一个变量 $ans$ ，保存构造前缀和的过程里，出现的最大值即可。

代码展示

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int ans = 0;
        int t = 0;
        for(auto x:gain){
            t +=x;
            ans = max(ans,t);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度 $O(n)$ ， $n$ 是 $gain$ 的长度，一次遍历构造前缀和的时间复杂度 $O(n)$。

空间复杂度 $O(1)$ ， 除若干变量使用的常量级空间，没有使用额外的线性空间 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC