給定一個由整數陣列表示的非負整數
digits，其中digits[i]是第i位數字，最高位在陣列開頭。將這個整數加一後回傳結果陣列。
Example:
Input: digits = [1,2,9] Output: [1,3,0]
Intuition
TIP
核心思路：從最低位開始加一，如果產生進位就繼續向前傳遞，全部進位完則前方補 1。
- 大部分情況只需要把最後一位加 1 即可
- 需要處理進位的情況，例如 [1,2,9] -> [1,3,0]
- 特殊情況：所有位都是 9（如 [9,9,9] -> [1,0,0,0]），需要擴展陣列長度
Approaches
1. Simulate Carry (general) — O(n) / O(1)
- Idea: 從最低位開始，加上進位值，計算新的進位和當前位的值
- Time:
O(n)- n 為陣列長度 - Space:
O(1)- 原地修改（最壞情況 O(n) 需要新陣列）
class Solution {
fun plusOne(digits: IntArray): IntArray {
var carry = 1
for (i in digits.lastIndex downTo 0) {
val sum = digits[i] + carry
digits[i] = sum % 10
carry = sum / 10
if (carry == 0) return digits
}
// 全部進位完還有剩餘進位，如 999 -> 1000
val result = IntArray(digits.size + 1)
result[0] = 1
return result
}
}⭐ 2. Simplified (optimized for plus-one) — O(n) / O(1)
- Idea: 由於只加 1，進位只可能是 0 或 1。如果當前位不是 9，加完就可以直接回傳；是 9 則設為 0 繼續
- Time:
O(n)- 最壞全是 9 - Space:
O(1)- 原地修改（最壞 O(n)）
class Solution {
fun plusOne(digits: IntArray): IntArray {
for (i in digits.lastIndex downTo 0) {
if (digits[i] < 9) {
digits[i]++
return digits
}
digits[i] = 0
}
// 走到這裡表示所有位都是 9
val result = IntArray(digits.size + 1)
result[0] = 1
return result
}
}WARNING
當所有位都是 9 時，新陣列只需要設 result[0] = 1，其餘位自動為 0（IntArray 預設值）。不需要額外複製。
🔑 Takeaways
- Pattern: 大數加法的簡化版，進位傳遞是核心邏輯
- Key trick: 針對「只加 1」的特殊性簡化邏輯——不是 9 就直接加、是 9 就變 0 繼續，比通用進位寫法更簡潔