杨辉三角 II 图解题解

杨辉三角 II 要你返回哪一行

杨辉三角第 0 行是 [1]，往下每行头尾都是 1，中间每个数等于正上方两个数相加。给你行号 rowIndex（从 0 开始数），返回第 rowIndex 行，例子 rowIndex=4 答案是 [1,4,6,4,1]。重点在附加要求：只用 O(rowIndex) 额外空间（大 O 记号，衡量用量随规模的增长），别把三角摊开存着。

为什么把整张三角存下来是浪费

按 118 的做法把每行都存进二维表，推到第 rowIndex 行，存下的数约等于三角形面积，是 O(rowIndex²) 的空间。可题目只问最后一行，前面的行都是推导路上的中转站，交答案时全用不上。为输出一行去存整张三角全是白占地方，题目把空间卡在 O(rowIndex) 就是在拦它。

一个一维数组凭什么就够用

相邻两行才有关系：这一行每个数只由上一行两个数加出来，更早的行推完就没用。既然只需上一行，就别开二维表，只拿一行数组反复覆盖——上一行的值就地改成这一行的值（原地更新，不另开新数组）。这种把二维表压成一行、拿新值盖旧值的写法叫滚动数组（只留用得上的一行）。空间从 O(rowIndex²) 掉到 O(rowIndex)。

为什么更新必须从右往左

每个数等于正上方两个数之和——上一行斜上方一个偏左（左肩）、一个偏右（右肩）。落到一维数组，新 row[j] 等于旧 row[j]（右肩）加左边一格旧 row[j-1]（左肩），即 row[j]+=row[j-1]。

麻烦在左边 row[j-1] 这一轮也要改。若从左往右，先把 row[1] 改成新值，等算 row[2] 读它当左肩时读到的是新值而非旧值，整行就错。从右往左则先动右边、再动左边，要读的 row[j-1] 还没被碰过，一定是旧值。

拿 rowIndex=4 把这行数组滚一遍

参考代码先把长度 rowIndex+1 的数组全填 1：[1,1,1,1,1]，外层从第 2 行推起，内层从右往左更新。推第 2 行：row[1] 加 row[0] 得 2，成 [1,2,1,1,1]。推第 3 行：先改 row[2]，左肩 row[1] 还是旧的 2，得 3；再改 row[1] 得 3，成 [1,3,3,1,1]。

推第 4 行：从右往左改 row[3]、row[2]、row[1]。row[3] 加左肩 3 得 4；轮到 row[2]，左肩 row[1] 仍是旧的 3，3 加 3 得 6，正是正中间那个 6；最后 row[1] 加 row[0] 得 4，定格 [1,4,6,4,1] 就是第 4 行。

方向写反会怎样，rowIndex 很小要不要特判

外层逐行、内层逐列，总更新次数约是三角形面积，时间 O(rowIndex²)；空间只有一个长 rowIndex+1 的数组，O(rowIndex)。方向写反是滚动数组最伤的一处：改成从左往右，左肩被这一轮新值污染，整行都坏，还不报错，只给你个看着对却错的结果。rowIndex=0 和 1 时，全填 1 后内层进不去，[1] 或 [1,1] 就是答案，不用特判。

Python

class Solution:
    def getRow(self, rowIndex):
        row = [1] * (rowIndex + 1)        # 一维数组，先全填 1
        for i in range(2, rowIndex + 1):  # 从第 2 行开始往下推
            for j in range(i - 1, 0, -1):  # 从右往左更新中间
                row[j] += row[j - 1]      # 当前 += 左肩(还是旧值)
        return row

C++

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1, 1);      // 一维数组，全填 1
        for (int i = 2; i <= rowIndex; i++) {
            for (int j = i - 1; j >= 1; j--) {   // 从右往左
                row[j] += row[j - 1];
            }
        }
        return row;
    }
};

Java

class Solution {
    public List<Integer> getRow(int rowIndex) {
        int[] row = new int[rowIndex + 1];
        Arrays.fill(row, 1);                  // 一维数组，全填 1
        for (int i = 2; i <= rowIndex; i++) {
            for (int j = i - 1; j >= 1; j--) {   // 从右往左
                row[j] += row[j - 1];
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int v : row) ans.add(v);
        return ans;
    }
}