LeetCode 66：Plus One（加一）

一、題目描述

給定非負整數數組 digits 表示一個整數（最高位在前），對該整數加一，返回新數組。

範例： [1,2,3] → [1,2,4]；[9,9] → [1,0,0]

二、解題思路：從末位模擬加法進位

從最後一位開始加 1，處理進位。若最高位處理完仍有進位，在數組頭部插入 1。

三、代碼實現（C++）

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

四、複雜度分析

• 時間：O(N)
• 空間：O(1) 或 O(N) (擴容時)

直接在原數組上修改，代碼簡潔高效。