119. 杨辉三角 II
题目描述
输入一个非负整数 rowIndex，返回杨辉三角中下标为 rowIndex 的那一行。行下标从 0 开始，第 0 行是 [1]。
杨辉三角每行首尾都是 1，中间每个数等于上一行中位于它左上和右上的两个数之和。
示例 1
输入：rowIndex = 3 输出：[1,3,3,1]
解释：第 0 到 3 行依次是 [1]、[1,1]、[1,2,1]、[1,3,3,1]。
示例 2
输入：rowIndex = 0 输出：[1]
解释：第 0 行只有一个 1。
示例 3
输入：rowIndex = 1 输出：[1,1]
解释：第 1 行是 [1,1]。
数据范围
0 <= rowIndex <= 33
进阶：能否只用 O(rowIndex) 的额外空间？
解题思路：一维数组倒序递推
只用一个数组 row，初始全为 1。从第 2 行开始，把它原地更新为下一行：row[j] += row[j-1]。关键是 j 从右往左遍历：更新 row[j] 时，row[j-1] 还是上一行的值。
为什么正确
外层循环第 i 轮结束时，row[0..i] 是杨辉三角第 i 行。
复杂度分析
时间 O(rowIndex²)，额外空间 O(1)（不计返回值）。
易错点
从左往右更新会出错：更新 row[j] 时 row[j-1] 已经是新行的值，结果会变成前缀和。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
row = [1] * (rowIndex + 1)
for i in range(2, rowIndex + 1):
for j in range(i - 1, 0, -1):
row[j] += row[j - 1]
return rowclass Solution {
public List<Integer> getRow(int rowIndex) {
int[] row = new int[rowIndex + 1];
Arrays.fill(row, 1);
for (int i = 2; i <= rowIndex; i++) {
for (int j = i - 1; j > 0; j--) {
row[j] += row[j - 1];
}
}
List<Integer> res = new ArrayList<>();
for (int v : row) res.add(v);
return res;
}
}class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + 1, 1);
for (int i = 2; i <= rowIndex; i++) {
for (int j = i - 1; j > 0; j--) {
row[j] += row[j - 1];
}
}
return row;
}
};func getRow(rowIndex int) []int {
row := make([]int, rowIndex+1)
for k := range row {
row[k] = 1
}
for i := 2; i <= rowIndex; i++ {
for j := i - 1; j > 0; j-- {
row[j] += row[j-1]
}
}
return row
}var getRow = function(rowIndex) {
const row = new Array(rowIndex + 1).fill(1);
for (let i = 2; i <= rowIndex; i++) {
for (let j = i - 1; j > 0; j--) {
row[j] += row[j - 1];
}
}
return row;
};function getRow(rowIndex: number): number[] {
const row = new Array(rowIndex + 1).fill(1);
for (let i = 2; i <= rowIndex; i++) {
for (let j = i - 1; j > 0; j--) {
row[j] += row[j - 1];
}
}
return row;
}其他解法
倒序递推只用加法，不存在溢出风险，但要 O(rowIndex²)；组合数递推是 O(rowIndex)，需要注意中间结果溢出。
解法 2：组合数线性递推 时间 O(rowIndex)，空间 O(1)
第 rowIndex 行第 k 个数是组合数 C(rowIndex, k)。相邻两项满足 C(n, k) = C(n, k-1) × (n-k+1) / k。从 row[0] = 1 出发依次算出整行，先乘后除可以保证整除。
只需一次遍历，比逐行递推快一个数量级。乘法的中间结果会超过 32 位整数，C++ 和 Java 要用 64 位整数计算。
from typing import List
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
row = [1] * (rowIndex + 1)
for k in range(1, rowIndex + 1):
row[k] = row[k - 1] * (rowIndex - k + 1) // k
return rowclass Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> row = new ArrayList<>();
row.add(1);
for (int k = 1; k <= rowIndex; k++) {
row.add((int)((long)row.get(k - 1) * (rowIndex - k + 1) / k));
}
return row;
}
}class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + 1, 1);
for (int k = 1; k <= rowIndex; k++) {
row[k] = (int)(1LL * row[k - 1] * (rowIndex - k + 1) / k);
}
return row;
}
};func getRow(rowIndex int) []int {
row := make([]int, rowIndex+1)
row[0] = 1
for k := 1; k <= rowIndex; k++ {
row[k] = row[k-1] * (rowIndex - k + 1) / k
}
return row
}var getRow = function(rowIndex) {
const row = new Array(rowIndex + 1).fill(1);
for (let k = 1; k <= rowIndex; k++) {
row[k] = row[k - 1] * (rowIndex - k + 1) / k;
}
return row;
};function getRow(rowIndex: number): number[] {
const row: number[] = new Array(rowIndex + 1).fill(1);
for (let k = 1; k <= rowIndex; k++) {
row[k] = row[k - 1] * (rowIndex - k + 1) / k;
}
return row;
}