LeetCode 118. 杨辉三角

约 4 分钟
文章信息 13 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 字节跳动 美团 快手 腾讯 百度 亚马逊 虾皮 LeetCode 热题 100
标签
数组 动态规划
目录

题目描述

✅ 118. 杨辉三角

image-20260329111344349

image-20260329111405989

image-20260329112208142

题意分析

输入只有一个整数 numRows，要求返回杨辉三角的前 numRows 行，输出是一个每行长度递增的二维列表。

题面用图示定义了生成规则：每一行的两端固定是 1，中间的每个数等于它「肩上」的两个数之和，也就是上一行相邻两个位置相加。规则本身没有歧义，真正的难点全在下标上——第几行有几个元素、中间部分从哪开始到哪结束。

约束 1 <= numRows <= 30 有两层含义：一是不存在 numRows = 0 的空输出，二是数值不会溢出（第 30 行的最大值约 7.7 亿，int 装得下），不需要用 long 或大数。

边界情况：numRows = 1 时只有一行 [1]；numRows = 2 时第二行是 [1,1]，中间元素个数为 0，任何访问「上一行」的代码在这一行都不该被执行到。

解法：按定义逐行递推

核心思路

杨辉三角每一行只依赖上一行：两端固定为 1，中间位置满足

current[col] = previous[col - 1] + previous[col]

题目要求返回前 numRows 行，上一行本来就保存在答案中，因此直接按定义递推最简单；组合数公式会额外引入乘除顺序和溢出问题，没有必要。

使用从 0 开始的行号后，第 row 行长度为 row + 1，合法下标是 0..row。循环不变量是：构造第 row 行前，答案中已经完整保存前 row 行；因此中间位置引用的两个上一行下标一定存在。首尾单独赋 1 后，递推式逐项生成，数学归纳即可证明所有行正确。

解题步骤

  1. 从第 0 行依次构造到第 numRows - 1 行。
  2. 为第 row 行创建长度为 row + 1 的容器。
  3. col == 0 或 col == row 时填 1。
  4. 其余位置填入上一行 col - 1 与 col 两项之和。
  5. 当前行完成后加入答案。

当 numRows = 5 时，各行依次为 [1]、[1,1]、[1,2,1]、[1,3,3,1]、[1,4,6,4,1]。第 0、1 行没有中间位置，主循环无需额外特判。

代码实现

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

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> answer = new ArrayList<>(numRows);

        for (int row = 0; row < numRows; row++) {
            List<Integer> current = new ArrayList<>(row + 1);
            for (int col = 0; col <= row; col++) {
                if (col == 0 || col == row) {
                    current.add(1);
                } else {
                    List<Integer> previous = answer.get(row - 1);
                    current.add(previous.get(col - 1) + previous.get(col));
                }
            }
            answer.add(current);
        }
        return answer;
    }
}

func generate(numRows int) [][]int {
    answer := make([][]int, 0, numRows)

    for row := 0; row < numRows; row++ {
        current := make([]int, row+1)
        current[0] = 1
        current[row] = 1

        for col := 1; col < row; col++ {
            current[col] = answer[row-1][col-1] + answer[row-1][col]
        }
        answer = append(answer, current)
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n^2)$，其中 $n$ 是 numRows；共生成 $n(n+1)/2$ 个元素。
  • 空间复杂度：$O(n^2)$，用于返回全部元素；若不计返回值，额外空间为 $O(1)$。

关键点总结

  • 递推式是题目定义的直接翻译，不需要组合数公式。
  • 第 row 行长度为 row + 1，两端下标是 0 和 row。
  • 只有 0 < col < row 时才读取上一行，所以下标天然安全。
  • 面试追问只返回第 k 行时，可用一维数组从右向左更新，将额外空间降为 $O(k)$。

易错点总结

  • 内层循环写成 col < row，会漏掉每行最后一个 1。
  • 只设置左端点，右端位置按递推读取会访问上一行越界。
  • 多行复用同一个可变列表，会让历史行被后续修改覆盖。
  • 从当前行而非上一行读取，会使用尚未生成的数据。
  • 一维原地优化若从左向右更新，会覆盖后面仍需使用的旧值。

相似题目

题目 难度 考察点
119. 杨辉三角 II 简单 一维滚动数组倒序更新
509. 斐波那契数 简单 线性递推与滚动变量
70. 爬楼梯 简单 递推式的计数建模