杨辉三角 II

存整张三角要 O(rowIndex²) 空间。可我们只要最后一行，前面的行算完就没用了——这就是优化的突破口：能不能只留一行？

关键是从右往左更新。新值 row[j] 需要旧的左肩 row[j-1]——只要先动右边、后动左边，左边还没被改，读到的就是旧值，一个数组就够了。

若从左往右：先把 row[1] 改了，等算 row[2]=row[2]+row[1] 时，row[1] 已是新值，污染了结果。从右往左则保证每次读到的左肩都还是上一行的旧值。

滚动数组 · 起点 row0 = [1]：我们开一个长度 5 的数组(rowIndex+1)。一开始只有第 0 格 = 1，代表第 0 行 [1]。灰色格子是后面才会激活的位置，盯住它们怎么一格格点亮、被填出数来。

推第 1 行 · 末尾添 1：往下推一行，先在末尾补个 1(杨辉三角每行最右都是 1)。现在数组前两格是 [1,1] = 第 1 行。第 1 行中间没有要加的数，直接成形。

推第 2 行 · 末尾添 1：推第 2 行，再在末尾补 1，暂时是 [1,1,1]。但中间那个 1 还不对——它该等于上一行的左肩+右肩。下面从右往左修它。

第 2 行 · row[1] += row[0]：更新 row[1]：它加上左边的 row[0]=1，从 1 变 2。第 2 行成形 = [1,2,1]。注意此时 row[0] 还是旧的 1，没被动过。

推第 3 行 · 末尾添 1：推第 3 行，末尾补 1，临时是 [1,2,1,1]。中间两个数(下标 2、1)要修。先修右边的 row[2]，再修 row[1]——顺序不能反。

第 3 行 · row[2] += row[1]：先更右边的 row[2]：加上左肩 row[1]=2(还是旧值!)，变成 3。此刻 row[1] 仍是 2，等下一步才轮到它。

第 3 行 · row[1] += row[0]：再更 row[1]：加上 row[0]=1 变 3。第 3 行成形 = [1,3,3,1]。看，右边先改完左边才改，左肩读到的一直是旧值，没被污染。

推第 4 行 · 末尾添 1：推到第 4 行(目标行)，末尾补最后一个 1，临时是 [1,3,3,1,1]。所有格子都激活了。接下来从右往左更新下标 3、2、1 三个数。

第 4 行 · row[3] += row[2]：最右先动 row[3]：加上左肩 row[2]=3，变 4。继续往左。

第 4 行 · row[2] += row[1]：row[2] 加上左肩 row[1]=3(仍是旧值)，变 6——这就是 [1,4,6,4,1] 正中间那个 6。

第 4 行 · row[1] += row[0]：最后更 row[1]：加 row[0]=1 变 4。数组定格为 [1,4,6,4,1]——这就是第 4 行答案!整个过程只用了一个数组。

完成 · 第 4 行：整个过程只用了一行数组，没存任何中间行。空间从 O(n²) 压到 O(n)，和题目要求对上了。

下面用一张三角表把刚才的滚动还原成整张杨辉三角，逐格填一遍，你会更清楚每个数是怎么从上一行加出来的。

三角表 · 第 0 行：把三角左对齐放进表格。第 0 行只有一个 1。注意每行左右两端都是 1，中间靠相加得来。

三角表 · 第 1 行 = [1,1]：第 1 行 = [1,1]，全是两端的 1。

三角表 · 第 2 行先放两端 1：每行先把两端的 1 摆好(下标 0 和末尾)，中间留空。下一步算中间。

三角表 · 第 2 行填中间：第 2 行中间那个数 = 上一行的左肩 1 + 右肩 1 = 2。所以第 2 行 = [1,2,1]，正好对上滚动数组里那一步。

三角表 · 第 3 行先放两端 1：第 3 行先摆两端的 1，中间两个空位等着由上一行 [1,2,1] 相邻相加。

三角表 · 第 3 行填中间：第 3 行中间两个数都由上一行 [1,2,1] 相邻相加得来:1+2=3、2+1=3。第 3 行 = [1,3,3,1]。

三角表 · 第 4 行先放两端 1：最后一行(答案行)先摆两端 1，中间留三个空位，由上一行 [1,3,3,1] 相邻相加填出。

三角表 · 第 4 行填中间(答案)：第 4 行由上一行 [1,3,3,1] 相邻相加:1+3=4、3+3=6、3+1=4，两端补 1，得 [1,4,6,4,1]。和滚动数组算出的完全一致——这就是答案。

边界三连：rowIndex=0 和 1 时内层循环根本不执行(全填 1 就是答案)，所以代码天然兼容这些边界，不用特判。

面试追问：把「一个数组够用的原因」和「组合数 O(n) 解法」答出来，是这题的加分点。