LeetCode 119 杨辉三角 II：獲取指定行的最優空間解法

問題描述

給定非負索引 k，返回帕斯卡三角形（楊輝三角）的第 k 行（從 0 開始計數）。例如 k = 3 返回 [1, 3, 3, 1]。要求僅使用 O(k) 額外空間。

遞推關係與空間優化

楊輝三角第 i 行第 j 個元素（0-based）滿足：C(i, j) = C(i-1, j-1) + C(i-1, j)，邊界 C(i, 0) = C(i, i) = 1。

直接生成整個三角形需 O(k²) 空間。觀察到第 i 行只依賴第 i-1 行，可用兩個一維數組滾動更新，空間降為 O(k)。更進一步，可原地逆序更新單個數組：

vector<int> getRow(int rowIndex) {
    vector<int> row(rowIndex + 1, 0);
    row[0] = 1;
    for (int i = 1; i <= rowIndex; ++i) {
        for (int j = i; j > 0; --j) {
            row[j] += row[j - 1];
        }
    }
    return row;
}

逆序遍歷保證 row[j-1] 仍是上一行的值，實現原地更新，空間複雜度 O(k)，時間 O(k²)。

原文代碼分析

提供的 Java 代碼使用 pre 和 next 兩個 ArrayList 滾動更新，邏輯正確但可簡化。pre 存當前行，next 構建下一行，每輪結束 pre.clear() 並複製 next 內容。雖然可行，但頻繁分配/清空列表有額外開銷，不如原地逆序更新高效。

數學性質拓展

第 k 行元素即二項式係數 C(k, 0), C(k, 1), ..., C(k, k)。可利用組合數遞推公式 C(k, j) = C(k, j-1) * (k - j + 1) / j 單次遍歷生成，時間 O(k)，但需注意整數除法精度（使用長整型或分數化簡）。

總結

本題考察對楊輝三角遞推關係的理解及空間優化技巧。原地逆序更新是最優雅的 O(k) 空間解法，代碼簡潔高效，面試中極具代表性。