LeetCode 日記 #011: 1732. Find the Highest Altitude｜Prefix Sum｜Greedy

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.

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.

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，所以從第二個真實高度來推導：

高度 = 當前高度 + 變化量

所以我們就必須拿原陣列的元素跟持續更新的高度來作為前綴和，並用貪心算法逐次的求最大值，更新進答案的變數內：

1. 前綴和 = 當前高度 + 變化量
2. 答案 = 前綴和中的最大值

題解

class Solution {
    public int largestAltitude(int[] gain) {
        int real = 0;
        int answer = 0;
        for (int i = 0; i < gain.length; i++) {
            real = gain[i] + real; // Prefix Sum
            answer = Math.max(answer, real); // Greedy
        }
        return answer;
    }
}