Java实现LeetCode Pascal's Triangle(杨辉三角)解析

阿麦

发布时间：2026-10-13 | 2人浏览过

原创

Pascal's Triangle（杨辉三角）是LeetCode中经典的矩阵生成问题。本文将深入解析基于Java的解题思路，重点讲解如何通过双层循环与递推公式高效生成杨辉三角的每一行数据。

核心目标与数学原理

题目的目标是给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。例如当 numRows = 5 时：

[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

要解决这个问题，首先需要明确两个核心性质：

边界条件：每一行的第一个和最后一个数字始终为 1。
递推关系：中间的数字 val(i, j) 等于上一行对应位置的两个数字之和，即 val(i-1, j-1) + val(i-1, j)。

虽然可以利用排列组合公式 C(n, k) 直接计算每个位置的数值（如第 i 行第 j 个值为 C(i, j)），但在编程实现中，利用加法递推的方式往往更直观且不易越界。不过，对于空间优化，我们可以采用单数组滚动更新的方式，即只记录当前行的状态，并在遍历过程中从后向前更新，从而将空间复杂度降至 O(N)。下面的代码采用了标准的二维结构生成法，逻辑清晰，便于理解。

环境准备

由于使用的是标准库进行集合操作，请确保运行环境支持以下Java组件：

java.util.ArrayList
java.util.List

在本地或在线编译器中创建一个新的 Java 类（如 PascalsTriangle.java）。

第1步：初始化结果容器

首先，创建一个外层的 List<List<Integer>> 作为最终返回的杨辉三角。
入口：主函数 main 或测试用例方法。
动作：实例化一个空列表 result，并传入 numRows 进行预分配以提高性能。

第2步：逐行生成与内部元素计算

目的：遍历行数 i，构建每一行的具体数字序列。
入口：外层 for 循环，范围 i = 0 至 i < numRows。
参数：numRows (总行数), i (当前行索引)。

在新的一行开始时，先添加一个固定的首元素 1。
如果 i > 0，则进入内层循环生成中间的数值。
关键算法：利用变量 temp 保存上一轮的结果，利用 temp * (i - j + 1) / j 这个组合数递推公式可以极快地计算出当前位置的值，避免了创建额外二维数组存储上一行的开销。此方法利用了 C(n, k) = C(n, k-1) * (n - k + 1) / k 的性质。

完整代码实现

以下是完整的 Java 实现代码，包含详细的逻辑注释：

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

public class PascalsTriangle {
    public static void main(String[] args) {
        // 测试用例，分别打印不同行数的结果
        System.out.println("numRows=1: " + generate(1));
        System.out.println("numRows=0: " + generate(0));
        System.out.println("numRows=5: " + generate(5));
    }

    /**
     * 生成 Pascal's Triangle 的主方法
     */
    public static List> generate(int numRows) {
        List> result = new ArrayList<>(numRows);
        
        for (int i = 0; i < numRows; i++) {
            List thisRow = new ArrayList<>(i + 1);
            
            // 每一行的第一个元素都是 1
            thisRow.add(1);
            
            // 计算当前行剩余的元素
            int temp = 1;
            for (int j = 1; j <= i; j++) {
                // 核心递推公式：利用上一元素的值推算当前元素值
                // 结合C(n,k)性质进行整型运算，防止溢出需注意long类型转换
                temp = temp * (i - j + 1) / j;
                thisRow.add(temp);
            }
            
            result.add(thisRow);
        }
        return result;
    }
}