118. 杨辉三角

题目链接：118. 杨辉三角

题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

核心思考：二维数组模拟构建

杨辉三角的构建可以直接通过双层循环进行模拟。在构建时，我们需要遵循它的几个直观几何和递推特征：

1. 第 i 行（索引从 0 起始计算）必定含有 i + 1 位内部元素。
2. 每行最左侧的头部元素和最右侧的尾巴元素数值必定为 1。
3. 行内中间范围的元素数值，等于其在上一行正上方对应位置元素 ans[i-1][j]、以及左上角元素 ans[i-1][j-1] 之和。

利用上述特性：

• 我们用外层循环负责依次生成每一行的基础一维列表并将其填充补全为 1。
• 然后利用内循环按需截取处理夹在这首尾两个固定 1 中间的空缺空档，套用上一行的数组计算得出当前数值。
• 处理结束后挂载进入外层存放集进行迭代。

解题思路 (Python)

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = []
        for i in range(numRows):
            line = [1] * (i + 1)
            line[0] = line[i] = 1
            if i >= 2:
                for j in range(1,i):
                    line[j] = ans[i-1][j] + ans[i-1][j-1]
            ans.append(line)
        return ans

复杂度分析

• 时间复杂度：$O(N^2)$，此处 $N$ 代表最终输出的 numRows。代码中包括了嵌套的两层循环过程用于逐排推导结构面积加和，相当于一个等差数列前 N 项和的次数。
• 空间复杂度：$O(1)$。我们仅仅执行在迭代结构层面的数组累积并查表推倒，除去用于接收保存应答反馈的返回集 ans 基本面外，没有动用其余的多余大规模空间。