118. 杨辉三角（Pascal’s Triangle）

频次 ★★ · 难度 🟢 · 高频：全厂

题目

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。每行第一个和最后一个元素为 1，中间元素等于上一行相邻两个元素之和。

示例：

输入: numRows = 5
输出: [
  [1],
  [1,1],
  [1,2,1],
  [1,3,3,1],
  [1,4,6,4,1]
]

思路

逐行构造：

• 第 i 行有 i+1 个元素
• 首尾固定为 1
• 中间元素 row[j] = prevRow[j-1] + prevRow[j]

代码

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        List<Integer> row = new ArrayList<>();
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) {
                row.add(1);
            } else {
                row.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
            }
        }
        result.add(row);
    }
    return result;
}

复杂度

• 时间：O(numRows²) — 第 i 行有 i 个元素，总计 1+2+…+n = O(n²)
• 空间：O(numRows²) — 输出结果占用，不计入则为 O(1) 额外空间

边界条件

• numRows == 0：循环不执行，返回空列表。
• numRows == 1：只生成 [[1]]，j == 0 == i 同时成立，走首尾分支，正确。

变式

• 只要求返回第 k 行（不需要整个三角形，如 LeetCode 119 题）：可以用一维数组从后往前更新（row[j] += row[j-1]），把空间从 O(k²) 降到 O(k)，避免存储之前所有行。
• 求某一行第 k 个数的组合数值（不生成整行）：直接用组合数公式 C(n, k) = n! / (k!(n-k)!)，避免逐行递推，适合只查询单点值的场景。

易错点

• result.get(i - 1) 依赖上一行已经生成完毕，行与行之间必须严格按顺序构造，不能用递归/并行乱序生成。
• 首尾判断 j == 0 || j == i 要在访问 result.get(i-1).get(j-1) 之前，否则 i == 0 时会越界访问不存在的第 -1 行。

面试追问

• 能不能省掉存储所有历史行的空间？ 如果只需要最终一行或逐行输出后不再需要之前的行，可以用一维数组原地更新（从后往前，避免覆盖还没用到的旧值），这是”滚动数组”思想的一个简单例子。
• 杨辉三角和组合数 C(n,k) 有什么关系？ 第 i 行第 j 列的值就是 C(i, j)，递推公式 C(i,j) = C(i-1,j-1) + C(i-1,j) 正是本题代码里的加法，理解这层关系能帮助快速联想到组合数学相关的题目。

关联题

• 进阶：119. 杨辉三角 II —— 只要第 k 行，倒序原地更新压到 O(k) 空间
• 知识点：递推填表是最朴素的动态规划，入门衔接见动态规划；每行也是组合数 C(n,k)