杨辉三角 II 图解题解

这道题到底在问什么

rowIndex

4

输出

[1,4,6,4,1]

解释

第 0 行 [1]，逐行往下推，第 4 行就是 [1,4,6,4,1]

最优解：一步一步想明白

1. 3存整张三角要 O(rowIndex²) 空间。可我们只要最后一行，前面的行算完就没用了——这就是优化的突破口：能不能只留一行？
2. 4关键是从右往左更新。新值 row[j] 需要旧的左肩 row[j-1]——只要先动右边、后动左边，左边还没被改，读到的就是旧值，一个数组就够了。
3. 5若从左往右：先把 row[1] 改了，等算 row[2]=row[2]+row[1] 时，row[1] 已是新值，污染了结果。从右往左则保证每次读到的左肩都还是上一行的旧值。
4. 6只激活第 0 格我们开一个长度 5 的数组(rowIndex+1)。一开始只有第 0 格 = 1，代表第 0 行 [1]。灰色格子是后面才会激活的位置，盯住它们怎么一格格点亮、被填出数来。
5. 7激活 slot 1 = 1往下推一行，先在末尾补个 1(杨辉三角每行最右都是 1)。现在数组前两格是 [1,1] = 第 1 行。第 1 行中间没有要加的数，直接成形。
6. 8激活 slot 2 = 1推第 2 行，再在末尾补 1，暂时是 [1,1,1]。但中间那个 1 还不对——它该等于上一行的左肩+右肩。下面从右往左修它。
7. 91 + 1 = 2更新 row[1]：它加上左边的 row[0]=1，从 1 变 2。第 2 行成形 = [1,2,1]。注意此时 row[0] 还是旧的 1，没被动过。
8. 10激活 slot 3 = 1推第 3 行，末尾补 1，临时是 [1,2,1,1]。中间两个数(下标 2、1)要修。先修右边的 row[2]，再修 row[1]——顺序不能反。
9. 111 + 2 = 3先更右边的 row[2]：加上左肩 row[1]=2(还是旧值!)，变成 3。此刻 row[1] 仍是 2，等下一步才轮到它。
10. 122 + 1 = 3再更 row[1]：加上 row[0]=1 变 3。第 3 行成形 = [1,3,3,1]。看，右边先改完左边才改，左肩读到的一直是旧值，没被污染。
11. 13激活 slot 4 = 1推到第 4 行(目标行)，末尾补最后一个 1，临时是 [1,3,3,1,1]。所有格子都激活了。接下来从右往左更新下标 3、2、1 三个数。
12. 141 + 3 = 4最右先动 row[3]：加上左肩 row[2]=3，变 4。继续往左。
13. 153 + 3 = 6row[2] 加上左肩 row[1]=3(仍是旧值)，变 6——这就是 [1,4,6,4,1] 正中间那个 6。
14. 163 + 1 = 4最后更 row[1]：加 row[0]=1 变 4。数组定格为 [1,4,6,4,1]——这就是第 4 行答案!整个过程只用了一个数组。
15. 17答案 = [1,4,6,4,1]整个过程只用了一行数组，没存任何中间行。空间从 O(n²) 压到 O(n)，和题目要求对上了。
16. 18下面用一张三角表把刚才的滚动还原成整张杨辉三角，逐格填一遍，你会更清楚每个数是怎么从上一行加出来的。
17. 19T[0][0] = 1把三角左对齐放进表格。第 0 行只有一个 1。注意每行左右两端都是 1，中间靠相加得来。
18. 20两端都是 1第 1 行 = [1,1]，全是两端的 1。
19. 21两端 = 1，中间待填每行先把两端的 1 摆好(下标 0 和末尾)，中间留空。下一步算中间。
20. 22T[2][1] = T[1][0]+T[1][1]第 2 行中间那个数 = 上一行的左肩 1 + 右肩 1 = 2。所以第 2 行 = [1,2,1]，正好对上滚动数组里那一步。
21. 23两端 = 1第 3 行先摆两端的 1，中间两个空位等着由上一行 [1,2,1] 相邻相加。
22. 24[1,3,3,1]第 3 行中间两个数都由上一行 [1,2,1] 相邻相加得来:1+2=3、2+1=3。第 3 行 = [1,3,3,1]。
23. 25两端 = 1最后一行(答案行)先摆两端 1，中间留三个空位，由上一行 [1,3,3,1] 相邻相加填出。
24. 26[1,4,6,4,1]第 4 行由上一行 [1,3,3,1] 相邻相加:1+3=4、3+3=6、3+1=4，两端补 1，得 [1,4,6,4,1]。和滚动数组算出的完全一致——这就是答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

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;
    }
};

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;
    }
}

复杂度

面试官可能追问