Find the Highest Altitude
題目描述
有 n+1 個點，起始海拔為 0。給定長度為 n 的陣列 gain，其中 gain[i] 是第 i 點到第 i+1 點的海拔變化。回傳最高海拔。
輸入：gain = [-5,1,5,0,-7]
輸出：1（海拔依序為 [0,-5,-4,1,1,-6]，最高為 1）
輸入：gain = [-4,-3,-2,-1,4,3,2]
輸出：0（起點 0 就是最高的）
解題思路
初始化
currentAlt = 0（起點海拔）, maxAlt = 0（起點也是候選最高點）
累加
遍歷 gain 陣列，每步 currentAlt += gain[i]。例如 gain[0]=-5 → currentAlt=-5
更新最大值
每步累加後比較 maxAlt = max(maxAlt, currentAlt)，追蹤到目前為止的最高海拔
回傳
遍歷完所有 gain 後，maxAlt 就是整趟旅程的最高海拔
程式碼
C#
public class Solution {
public int LargestAltitude(int[] gain) {
int current = 0, max = 0;
foreach (int g in gain) {
current += g;
if (current > max) max = current;
}
return max;
}
}TypeScript
function largestAltitude(gain: number[]): number {
let current = 0, max = 0;
for (const g of gain) {
current += g;
if (current > max) max = current;
}
return max;
}Python
def largestAltitude(gain: list[int]) -> int:
current = max_alt = 0
for g in gain:
current += g
max_alt = max(max_alt, current)
return max_alt複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |
遍歷 gain 陣列一次，每步做一次加法和一次比較，因此時間 O(n)。只用兩個變數追蹤當前海拔和最大海拔，空間 O(1)。
邊界情況
- 一路下坡：例如
gain = [-1,-2,-3]，海拔依序為 [0,-1,-3,-6]，起點 0 就是最高點 - gain 只有一個元素：例如
gain = [5]，海拔為 [0,5]，最高點為 5 - 全部為零：例如
gain = [0,0,0]，海拔永遠是 0，回傳 0
圖解
圖表展示前綴和的累加過程：起點為 0，依序加上 -5, 1, 5, 0, -7 得到海拔序列。過程中海拔在第 3 和第 4 個點達到最高值 1，最終回傳 1。
進階觀點
💡面試追問
-
Q: 這其實就是前綴和（Prefix Sum）嗎？ A: 對，海拔序列就是 gain 陣列的前綴和。
altitude[i] = gain[0] + gain[1] + ... + gain[i-1]。這題是前綴和的最基礎應用，只需追蹤累加過程中的最大值。 -
Q: 為什麼 maxAlt 初始值是 0？ A: 因為起點海拔為 0，起點本身就是一個候選答案。如果 gain 全是負數（一路下坡），起點就是最高點，maxAlt 必須包含起點。
-
Q: 如果起點不是 0 怎麼辦？ A: 將 currentAlt 和 maxAlt 都初始化為起點值即可，其餘邏輯不變。
理解測驗
🤔 為什麼初始的 maxAlt 要設為 0 而不是負無窮？
🤔 gain = [1,2,3] 時，各點海拔依序是什麼？