杨辉三角问题描述

LeetCode 118题要求生成一个指定行数的杨辉三角。杨辉三角的特点是每个数等于它上方两数之和，首尾元素恒为1。例如前5行如下：

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

顺序表构建方法

使用Java的ArrayList实现动态二维数组结构。外层列表存储每一行的内层列表，内层列表存储具体数字。

List<List<Integer>> triangle = new ArrayList<>();

元素填充技巧

初始化首行：直接添加只有一个元素1的列表。

triangle.add(new ArrayList<>(Arrays.asList(1)));

递推填充后续行：

1. 每行首位和末位固定为1
2. 中间元素通过上一行的相邻元素求和得到

for (int row = 1; row < numRows; row++) {
    List<Integer> prevRow = triangle.get(row - 1);
    List<Integer> currentRow = new ArrayList<>();
    
    currentRow.add(1); // 行首元素
    for (int col = 1; col < row; col++) {
        currentRow.add(prevRow.get(col-1) + prevRow.get(col));
    }
    currentRow.add(1); // 行尾元素
    
    triangle.add(currentRow);
}

时间复杂度分析

• 时间复杂度：O(n²)，需要填充n(n+1)/2个元素
• 空间复杂度：O(n²)，存储整个三角形所需空间

边界处理

当输入为0时返回空列表：

if (numRows == 0) return new ArrayList<>();

完整实现代码

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();
        if (numRows == 0) return triangle;
        
        triangle.add(new ArrayList<>(Arrays.asList(1)));
        
        for (int row = 1; row < numRows; row++) {
            List<Integer> prevRow = triangle.get(row - 1);
            List<Integer> currentRow = new ArrayList<>();
            
            currentRow.add(1);
            for (int col = 1; col < row; col++) {
                currentRow.add(prevRow.get(col-1) + prevRow.get(col));
            }
            currentRow.add(1);
            
            triangle.add(currentRow);
        }
        return triangle;
    }
}