LeetCode 119. 杨辉三角 II

Categories:

题目描述
思路分析
1. 解法一：滚动数组（推荐）
相似题目

题目描述

✅ 119. 杨辉三角 II

思路分析

解法一：滚动数组（推荐）

核心思路：

第 k 行只依赖上一行，可用一维数组从右向左更新。

初始化 row[0] = 1，每行更新 row[j] = row[j] + row[j-1]。

右向左更新保证使用的是上一行的值。

复杂度分析：

时间复杂度：O(k^2)，其中 k 表示行号。

空间复杂度：O(k)，仅使用一维数组。

class Solution {
    public List<Integer> getRow(int rowIndex) {
        Integer[] row = new Integer[rowIndex + 1];
        Arrays.fill(row, 0);
        row[0] = 1;

        for (int i = 1; i <= rowIndex; i++) {
            // 从右向左更新，避免覆盖上一行数据
            for (int j = i; j >= 1; j--) {
                row[j] = row[j] + row[j - 1];
            }
        }

        return Arrays.asList(row);
    }
}

func getRow(rowIndex int) []int {
	row := make([]int, rowIndex+1)
	row[0] = 1

	for i := 1; i <= rowIndex; i++ {
		// 从右向左更新，避免覆盖上一行数据
		for j := i; j >= 1; j-- {
			row[j] = row[j] + row[j-1]
		}
	}

	return row
}

相似题目

题目	难度	考察点
118. 杨辉三角	简单	动态规划
119. 杨辉三角 II	简单	滚动数组
120. 三角形最小路径和	中等	DP
64. 最小路径和	中等	DP
746. 使用最小花费爬楼梯	简单	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/67884119