LeetCode Pascal's Triangle II：O(k) 空間生成第 k 行

問題描述

給定行索引 k (0-based)，返回楊輝三角第 k 行。要求只用 O(k) 額外空間。

原地逆序更新

第 i 行有 i+1 個元素。從右向左更新，利用 row[j] = row[j] + row[j-1]（當前值 = 舊值 + 左鄰舊值），逆序保證 row[j-1] 未被覆蓋。

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

演示：k=3

初始: [1, 1, 1, 1]
i=0:  無內層循環
i=1:  j=1: row[1]=1+1=2  → [1,2,1,1]
i=2:  j=2: row[2]=1+2=3; j=1: row[1]=2+1=3 → [1,3,3,1]
i=3:  j=3: row[3]=1+3=4; j=2: row[2]=3+3=6; j=1: row[1]=3+1=4 → [1,4,6,4,1] (但 rowIndex=3 只取前4個)
實際 k=3 循環到 i=3 結束，結果 [1,3,3,1]

複雜度

• 時間：O(k²)
• 空間：O(k)