问题描述

杨辉三角（Pascal's Triangle）是一个经典的数学图形，第 i 行第 j 列的值等于第 i-1 行第 j-1 列与第 j 列的和。LeetCode 题目要求生成前 numRows 行的杨辉三角，并以 List<List<Integer>> 形式返回。

核心思路

使用顺序表（Java 中的 ArrayList）逐行生成杨辉三角。每一行的值依赖于上一行的值，首尾元素固定为 1，中间元素通过动态计算得到。

实现代码

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

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();
        
        for (int row = 0; row < numRows; row++) {
            List<Integer> currentRow = new ArrayList<>();
            
            // 每一行的首尾元素为1
            currentRow.add(1);
            
            // 中间元素通过上一行的相邻元素计算
            if (row > 0) {
                List<Integer> prevRow = triangle.get(row - 1);
                for (int col = 1; col < prevRow.size(); col++) {
                    currentRow.add(prevRow.get(col - 1) + prevRow.get(col));
                }
                currentRow.add(1);
            }
            
            triangle.add(currentRow);
        }
        return triangle;
    }
}

代码解析

1. 初始化结果列表
   triangle 用于存储所有行的杨辉三角数据，类型为 List<List<Integer>>。

2. 逐行生成
   外层循环控制行数，从第 0 行到第 numRows-1 行。

3. 处理当前行

   • 首元素直接赋值为 1。
   • 若当前行不是第 0 行，通过上一行的相邻元素求和生成中间元素。
   • 尾元素固定为 1。

4. 添加到结果
   将当前行 currentRow 加入 triangle。

复杂度分析

• 时间复杂度：O(numRows²)，需要嵌套循环逐行生成。
• 空间复杂度：O(numRows²)，存储所有行的数据。

边界情况

• 输入为 0 时，返回空列表。
• 输入为 1 时，返回 [[1]]。
• 输入为 5 时，返回经典的 5 行杨辉三角。

测试示例

public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.generate(5));
}

输出：

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

优化与变种

• 空间优化：若只需返回第 n 行，可用滚动数组将空间复杂度降至 O(n)。
• 数学公式法：利用组合数公式直接计算每个位置的值，适用于单行查询。