119. 杨辉三角 II

🟢   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal 's triangle.

In Pascal 's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: rowIndex = 3

Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0

Output: [1]

Example 3:

Input: rowIndex = 1

Output: [1,1]

Constraints:

• 0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

题目大意

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: rowIndex = 3

输出: [1,3,3,1]

示例 2:

输入: rowIndex = 0

输出: [1]

示例 3:

输入: rowIndex = 1

输出: [1,1]

提示:

• 0 <= rowIndex <= 33

进阶：

你可以优化你的算法到 O(rowIndex) 空间复杂度吗？

解题思路

杨辉三角的性质：

• 杨辉三角第 i 行的第 j 个元素可以通过 前一行 的第 j-1 和第 j 个元素相加得到。
  • arr[j] = arr[j] + arr[j-1]
• 每一行的第一个和最后一个元素永远是 1。
• 第 k 行有 k+1 个元素，索引从 0 开始。

1. 初始化数组 创建一个长度为 rowIndex + 1 的数组 arr，并将所有元素初始化为 1（因为每行的两端元素始终为 1）。

2. 遍历行数 从第 2 行开始（i = 2），因为第 0 行和第 1 行的元素都是 1。

3. 动态更新当前行 从索引 i - 1 到 1，逐步更新数组元素。从右向左更新数组，避免当前元素被覆盖，影响后续计算。

4. 返回结果 遍历完成后，arr 就是第 rowIndex 行的结果。

复杂度分析

• 时间复杂度：O(rowIndex^2)，需要两层遍历。
• 空间复杂度：O(rowIndex)，使用了一个数组 arr 来保存计算过程和结果。

代码

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function (rowIndex) {
	// 初始化一个长度为 rowIndex + 1 的数组，所有元素为 1
	let arr = new Array(rowIndex + 1).fill(1);

	// 从第 2 行开始遍历，计算每一行的中间元素
	for (let i = 2; i <= rowIndex; i++) {
		// 从右向左更新数组，避免当前元素被覆盖
		for (let j = i - 1; j > 0; j--) {
			arr[j] += arr[j - 1];
		}
	}

	// 返回第 rowIndex 行
	return arr;
};

相关题目

题号	标题	题解	标签	难度	力扣
118	杨辉三角	[✓]	数组 动态规划	🟢	🀄️ 🔗
2221	数组的三角和		数组 数学 组合数学 1+	🟠	🀄️ 🔗