LeetCode 66 Plus One：數組表示整數加一

題目大意

非負整數以數組形式存儲（最高位在前），如 [1,0,9] 代表 109。實現加 1 操作，返回新數組。

方法一：從末位模擬進位（推薦）

• 從最後一位開始，加 1，處理進位。
• 若最高位仍有進位，在數組頭部插入 1。
• 用 `vector::insert(begin(), val)` 或反向存儲後 `push_back` 最後 `reverse`。

代碼（反向存儲優化）

class Solution {
public:
    vector plusOne(vector& digits) {
        int n = digits.size();
        vector res;
        res.reserve(n+1);
        int carry = 1;
        for (int i = n-1; i >= 0; --i) {
            int sum = digits[i] + carry;
            res.push_back(sum % 10);
            carry = sum / 10;
        }
        if (carry) res.push_back(carry);
        reverse(res.begin(), res.end());
        return res;
    }
};

方法二：原地修改（若允許修改輸入）

for (int i = n-1; i >= 0 && carry; --i) {
    digits[i] += carry;
    carry = digits[i] / 10;
    digits[i] %= 10;
}
if (carry) digits.insert(digits.begin(), 1);
return digits;

複雜度

• 時間：O(n)。
• 空間：O(n) 結果數組（或 O(1) 原地）。

總結

Plus One 是大整數加法的最簡形式。**從低位向高位模擬進位** 是通用大整數加法的核心邏輯。反向存儲避免了 `vector::insert(begin())` 的 O(n²) 移動開銷，是工程優化的好習慣。