119. 杨辉三角 II

题目链接（简单）

题目描述

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

数据范围：

• 0 <= rowIndex <= 33

进阶：你可以优化你的算法到 O(rowIndex) 空间复杂度吗？

示例

示例 1：

输入： rowIndex = 3
输出： [1,3,3,1]

示例 2：

输入： rowIndex = 0
输出： [1]

示例 3：

输入： rowIndex = 1
输出： [1,1]

核心思路

本题和 LC 118 的区别：只需要返回第 rowIndex 行，不需要保存前面所有行。

三种解法：

1. 逐行递推：和 LC 118 一样生成所有行，最后取第 rowIndex 行，空间 $O(n^2)$；
2. 一维数组原地更新：只用一个长度为 rowIndex + 1 的数组，从右往左更新，空间 $O(n)$；
3. 组合数递推：第 rowIndex 行第 c 列 = $\binom{rowIndex}{c}$，用递推公式逐个算，空间 $O(n)$。

进阶要求 $O(rowIndex)$ 空间，方法二和方法三都满足。

方法一：逐行递推（$O(n^2)$ 空间，不推荐）

思路及解法

和 LC 118 完全一样，生成前 rowIndex + 1 行，返回最后一行。

代码

class Solution:
    def getRow(self, rowIndex: int) -> list[int]:
        ans = []
        for i in range(rowIndex + 1):
            cur = [1] * (i + 1)
            for j in range(1, i):
                cur[j] = ans[i - 1][j - 1] + ans[i - 1][j]
            ans.append(cur)
        return ans[rowIndex]

复杂度分析

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n^2)$，保存了所有行。

不满足进阶要求，但代码最简单，可以先讲这个作为开场。

方法二：一维数组原地更新（$O(n)$ 空间，推荐）

思路及解法

只用一个长度为 rowIndex + 1 的数组 row，初始全为 1。

关键：从第 1 行开始，逐行更新 row。第 i 行只有前 i + 1 个元素有效。

更新公式：

$$\text{row}[j] = \text{row}[j] + \text{row}[j-1]$$

为什么必须从右往左更新：

• row[j] 的新值依赖 row[j-1] 的旧值；
• 如果从左往右更新，row[j-1] 已经被更新成新值，row[j] 就会用到错误的数据；
• 从右往左更新时，row[j-1] 还没被更新，仍然是上一行的值。

举例：rowIndex = 4，初始 row = [1, 1, 1, 1, 1]

行 i	更新范围 j	更新后 row（前 i+1 位有效）
1	j = 1	[1, 2, 1, 1, 1]
2	j = 2, 1	[1, 3, 3, 1, 1]
3	j = 3, 2, 1	[1, 4, 6, 4, 1]
4	j = 4, 3, 2, 1	[1, 5, 10, 10, 5]（实际只需到 i=4）

最终 row = [1, 4, 6, 4, 1]，即第 4 行。

代码

class Solution:
    def getRow(self, rowIndex: int) -> list[int]:
        row = [1] * (rowIndex + 1)

        for i in range(1, rowIndex + 1):
            # 从右往左更新，避免覆盖还没用到的旧值
            for j in range(i - 1, 0, -1):
                row[j] = row[j] + row[j - 1]

        return row

注意内层范围：range(i - 1, 0, -1)，即 j 从 i - 1 到 1：

• j = i 是行末，始终为 1，不需要更新；
• j = 0 是行首，始终为 1，不需要更新；
• 中间 j = 1 到 i - 1 才需要更新。

复杂度分析

• 时间复杂度：$O(n^2)$，第 i 行更新 i - 1 次，共 $\frac{n(n-1)}{2}$ 次。
• 空间复杂度：$O(n)$，只用一个长度为 rowIndex + 1 的数组，满足进阶要求。

方法三：组合数递推（$O(n)$ 空间，也可行）

思路及解法

杨辉三角第 rowIndex 行第 c 列 = $\binom{rowIndex}{c}$。

利用组合数递推：

$$\binom{n}{c+1} = \binom{n}{c} \cdot \frac{n - c}{c + 1}$$

从 $\binom{n}{0} = 1$ 出发，依次算出 $\binom{n}{1}, \binom{n}{2}, \dots, \binom{n}{n}$，存入数组。

代码

class Solution:
    def getRow(self, rowIndex: int) -> list[int]:
        n = rowIndex
        row = [1] * (n + 1)
        comb = 1

        for c in range(n):
            comb = comb * (n - c) // (c + 1)
            row[c + 1] = comb

        return row

复杂度分析

• 时间复杂度：$O(n)$，只需遍历一次。
• 空间复杂度：$O(n)$，结果数组。

比方法二更快：方法二是 $O(n^2)$，方法三是 $O(n)$。

注意整除顺序：comb * (n - c) // (c + 1) 先乘后除，保证整除，不会丢精度。

三种方法对比

方法	时间	空间	是否满足进阶	特点
逐行递推	$O(n^2)$	$O(n^2)$	❌	思路最直观，但空间浪费
一维原地更新	$O(n^2)$	$O(n)$	✅	经典滚动数组，从右往左更新
组合数递推	$O(n)$	$O(n)$	✅	时间最优，代码短

推荐：

• 面试开场：先讲方法一，与 LC 118 自然衔接；
• 追问优化空间：讲方法二，展示滚动数组技巧；
• 追问优化时间：讲方法三，展示组合数递推，时间 $O(n)$ 最优。

关键细节

1. 方法二为什么从右往左更新

row[j] = row[j] + row[j-1]：

• 若从左往右，row[j-1] 已经被更新为第 i 行的值，row[j] 用的是新值 + 新值，错误；
• 若从右往左，row[j-1] 还是第 i-1 行的值，row[j] 用的是旧值 + 旧值，正确。

2. 方法二内层循环范围

range(i - 1, 0, -1)：

• j = i 是行末的 1，不需要更新；
• j = 0 是行首的 1，不需要更新；
• 中间 j = 1 到 i - 1 需要更新。

如果写成 range(i, 0, -1) 也能过，只是多算了一次 row[i] = row[i] + row[i-1]，但因为 row[i] = 1、row[i-1] 是上一行的值，结果不一定对。必须排除 j = i。

3. 方法三的整除

comb = comb * (n - c) // (c + 1)

必须先乘后除：

• 先乘：comb * (n - c) 一定能被 (c + 1) 整除（组合数性质）；
• 后除：// 整数除法。

如果写成 comb * ((n - c) // (c + 1))，可能因 (n - c) 不能整除 (c + 1) 而丢精度。

4. 方法三与 LC 118 的关系

LC 118 用逐行递推，每行之间互相依赖；方法三用组合数公式，行与行之间无依赖，直接算第 rowIndex 行，所以时间 $O(n)$ 而不是 $O(n^2)$。

代价：需要理解组合数递推公式。如果对组合数不熟，用方法二更稳妥。

5. 边界情况

• rowIndex = 0：返回 [1]；
• rowIndex = 1：返回 [1, 1]；
• 三个方法都能正确处理，无需特判。

6. 为什么方法二比方法三慢

方法二需要从第 1 行推到第 rowIndex 行，每行更新 i - 1 次，总共 $O(n^2)$。

方法三直接算第 rowIndex 行的每个组合数，$O(n)$ 就能完成。

总结

• 核心规律：第 rowIndex 行 = 组合数 $\binom{rowIndex}{c}$；
• 方法一（逐行递推）：$O(n^2)$ 时间、$O(n^2)$ 空间，最简单；
• 方法二（原地更新）：$O(n^2)$ 时间、$O(n)$ 空间，从右往左更新，满足进阶；
• 方法三（组合数）：$O(n)$ 时间、$O(n)$ 空间，时间最优；
• 易错点：
  • 方法二必须从右往左，否则覆盖旧值；
  • 方法三必须先乘后除，否则丢精度；
• 通用套路：「杨辉三角第 k 行」→ 组合数递推，$O(n)$ 时间最优。

相关题目

• LC 118. 杨辉三角（生成所有行，$O(n^2)$）
• LC 62. 不同路径（组合数应用）