前綴和應用: 尋找旅途中的海拔最高點_Leetcode #1732 精選75題解析

Rohit Tandon on Unsplash

題目敘述

假想一位自行車手正在公路旅行，旅行起始點從海拔為0的地方開始出發，給定每個紀錄點的高度位移向量陣列gain，請問整趟旅途中的海拔最高點是多少?

題目的原文敘述

測試範例

Example 1:

Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.
每個記錄點的高度分別為​[0,-5,-4,1,1,-6]
最高高度是1

Example 2:

Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.
每個記錄點的高度分別為[0,-4,-7,-9,-10,-6,-3,-1]
最高高度是0

演算法

題目的每個紀錄點的高度位移向量陣列gain，又說起始點的高度為0。

那麼，只要依序累加每個紀錄點的位移向量，就能得到每個紀錄點的海拔高度。

每回合迭代的時候，動態更新當下記錄到的高度，並且維護整趟旅途的海拔高度最大值。

程式碼

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        
        # altitude of current point
        cur = 0

        # global record of highest altitude
        highest = 0

        for offset in gain:

            # compute altitude for current point
            cur += offset

            # update global highest altitude
            highest = max(highest, cur)
        
        return highest

複雜度分析

時間複雜度:

從頭到尾掃描過每個陣列元素，所需時間為O(n)。

空間複雜度:

所使用到的都是固定尺寸的臨時變數，所佔用的記憶體空間為O(1)。

Reference:

[1] Python O(n) by linear scan [w/ Visualization]