LeetCode 119. 杨辉三角 II

约 4 分钟
文章信息 8 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 5-10 字节跳动 微软 美团
标签
数组 动态规划
目录

题目描述

✅ 119. 杨辉三角 II

image-20230312124142173

img

image-20230312124147762

题意分析

给一个行号 rowIndex，只要返回杨辉三角的这一行，前面的行不必输出。行号从 0 开始计数，第 0 行是 [1]，第 1 行是 [1, 1]，第 3 行是 [1, 3, 3, 1]，所以第 rowIndex 行恰好有 rowIndex + 1 个数。

三角形的构造规则是：每行首尾都是 1，中间每个位置等于它正上方与左上方两个数之和。注意这条规则只跨越相邻两行，第 i 行完全由第 i - 1 行决定，与更早的行无关。

「只要一行」是本题相对上一道题最关键的差异，也是空间优化的入口。题目进阶还要求只用 O(rowIndex) 的额外空间，等于明说不能把整个三角形都存下来。边界方面，rowIndex 可以取 0，此时答案是单个 1；行号上限在三十出头，最大的那个数不会超过 32 位整数范围，不必担心溢出。

解法：组合数递推

核心思路

问题关键： 第 k 行的第 j 个数就是组合数 C(k,j)。既然只要一行，就没有必要构造前面的所有行。

相邻组合数满足：

\[C(k,0)=1,\qquad C(k,j+1)=C(k,j)\times\frac{k-j}{j+1}\]

因此从 1 开始即可按顺序推出整行。相比一维逆序动态规划的 $O(k^2)$ 时间，组合数递推只需 $O(k)$ 时间。

正确性： 初值是 C(k,0)。若当前值为 C(k,j)，根据组合数定义约去公共阶乘后，递推式计算出的下一项恰为 C(k,j+1)；由归纳法，写入的 k+1 项全部正确。

溢出处理： 题目范围内最终系数能放入 32 位整数，但“当前系数乘以 k-j”的中间结果可能超出 32 位，所以先用 64 位完成乘法和除法，再转换为结果类型。

解题步骤

  1. 创建长度为 rowIndex + 1 的结果，令当前组合数 value = 1。
  2. 从 j = 0 到 rowIndex，先写入当前的 C(rowIndex,j)。
  3. 用 value = value * (rowIndex - j) / (j + 1) 推出下一项。
  4. 返回结果。

口述示例： rowIndex = 4 时，从 1 开始依次乘除：1 -> 4 -> 6 -> 4 -> 1，得到 [1,4,6,4,1]。

边界： rowIndex = 0 时只写入初值 1。每一步的数学结果都是整数，但必须先乘后除；提前做整数除法会截断。

代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>(rowIndex + 1);
        long value = 1;

        for (int j = 0; j <= rowIndex; j++) {
            row.add((int) value);
            value = value * (rowIndex - j) / (j + 1);
        }
        return row;
    }
}

func getRow(rowIndex int) []int {
    row := make([]int, rowIndex+1)
    value := int64(1)

    for j := 0; j <= rowIndex; j++ {
        row[j] = int(value)
        value = value * int64(rowIndex-j) / int64(j+1)
    }
    return row
}

复杂度分析

  • 时间复杂度：$O(k)$，其中 k = rowIndex，每个结果只计算一次。
  • 空间复杂度：$O(1)$ 额外空间；返回数组本身占 $O(k)$。

关键点总结

  • 杨辉三角第 k 行可直接视为组合数序列。
  • 相邻组合数递推避免了构造整个三角形，也优于 $O(k^2)$ 的滚动动态规划。
  • 乘法必须使用 64 位中间变量，转换只发生在最终系数写入时。
  • 先乘后除可保持整数结果；调换顺序会因截断丢失精度。

易错点总结

  • 将行号按 1 开始理解：第 0 行应为 [1]，结果长度是 rowIndex + 1。
  • 用阶乘分别计算组合数：阶乘更早溢出，并重复做大量计算。
  • 使用 32 位变量计算乘积：最终系数合法，中间乘积仍可能溢出。
  • 写成 value / (j + 1) * (rowIndex - j)：整数除法提前截断，例如 C(4,1) 推下一项时会算错。

相似题目

题目 难度 考察点
118. 杨辉三角 简单 要输出全部行，反而不能压维，重点在逐行构造与首尾补 1
120. 三角形最小路径和 中等 同样是三角形上的一维滚动，但自底向上推进可省去边界特判
62. 不同路径 中等 答案本身就是组合数，可对照递推解法与公式解法的取舍
64. 最小路径和 中等 依赖上方与左方两个格子，压成一维时遍历方向必须从左往右