题目描述
思路解析
一句话答案：LeetCode 119 杨辉三角 II 只要第 rowIndex 行，用滚动数组：一维数组从右往左原地更新 row[j]+=row[j-1]，方向反了会污染左肩。时间 O(rowIndex²)、空间压到 O(rowIndex)。
杨辉三角 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] 就是答案，不用特判。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
存整张三角要 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) 解法」答出来，是这题的加分点。
参考代码
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复杂度
- 时间复杂度：O(rowIndex²)，外层逐行、内层逐列，总更新次数约是三角形面积
- 空间复杂度：O(rowIndex)，只用一个长 rowIndex+1 的数组，没存整张三角
易错点
面试追问把动画讲成自己的话
追问为什么一个数组就够，不会算错？
追问能不能用组合数 O(rowIndex) 时间直接算？
追问和杨辉三角 I(返回整张三角)有什么区别？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
比特位计数
LeetCode 338 · 简单 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题