📘 題目敘述
一位騎士從海拔 0 開始騎自行車。
給定一個整數陣列 gain，其中 gain[i] 代表從第 i 個點騎到第 i + 1 個點時，海拔的變化量。
請你回傳在整段騎行過程中，所能到達的最高海拔高度。
條件限制
1 <= gain.length <= 100-100 <= gain[i] <= 100
🧠 解題思路
這題本質上就是在做一個「前綴和（prefix sum）」的過程：
- 從海拔
0開始 - 依序把每一段的高度變化
gain[i]加上去 - 在過程中隨時記錄「目前最高的海拔」
因為題目只在乎「最高到過哪裡」，
所以我們不需要存下所有高度，只要邊走邊更新最大值即可。
所有變數
gain：每一段路程的高度變化量now：- 目前所在位置的海拔高度
- 初始為
0
ans：- 到目前為止出現過的最高海拔
- 初始為
0
i：用來掃描gain陣列的索引
🪜 主要流程步驟
第一步：初始化高度
now = 0- 代表起點的海拔高度
ans = 0- 因為起點本身也是一個可能的最高點
第二步：依序累加高度變化
從左到右掃描 gain：
- 每一輪：
now += gain[i]- → 更新目前的海拔高度
ans = max(ans, now)- → 如果現在高度比之前都高，就更新答案
這樣可以確保：
- 所有經過的高度都被考慮過
ans永遠是目前為止的最高值
第三步：回傳最高海拔
- 迴圈結束後
ans就是整趟騎行中能到達的最高海拔- 直接回傳即可
💡 為什麼這樣做是正確的？
- 高度變化是「累積性」的 → 適合用前綴和
- 題目只要最大值，不需要保存整個高度序列
- 時間複雜度
O(n)、空間複雜度O(1) - 寫法直觀、好理解，也很符合題意
💻 程式碼實作
class Solution {
public:
int largestAltitude(vector<int>& gain) {
int now = 0;
int ans = 0;
for (int i = 0; i < gain.size(); i++) {
now += gain[i];
ans = max(ans, now);
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/find-the-highest-altitude/