LeetCode Pascal's Triangle II — O(k) 空間逐行原地構造

題目

給定 rowIndex (0-based)，回傳楊輝三角第 rowIndex 行，空間複雜度 O(k)。
例：k=3 → [1,3,3,1]。

核心技巧：從後向前更新

第 i 行長度 i+1。若從前向後更新，會覆蓋下一輪所需的舊值。反向迴圈 可原地覆蓋：
result[j] += result[j-1] (j 從 i 遞減至 1)。

Python 實作

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row = [1] * (rowIndex + 1)
        for i in range(2, rowIndex + 1):
            for j in range(i, 0, -1):   # 關鍵：逆序
                row[j] += row[j - 1]
        return row

複雜度

• 時間：O(k²)，k ≤ 33 極小。
• 空間：O(k)，僅一個長度 k+1 陣列。

變體延伸

• 若需輸出前 k 行（Pascal's Triangle I），同理逐行構造並存入二維列表。
• 組合數公式 C(n,k) = C(n,k-1)*(n-k+1)/k 可 O(k) 時間單行生成，但涉及除法需注意整數溢位。