1646. 获取生成数组中的最大值

🟢   🔖  数组 模拟  🔗 力扣 LeetCode

题目

You are given an integer n. A 0-indexed integer array nums of length n + 1 is generated in the following way:

• nums[0] = 0
• nums[1] = 1
• nums[2 * i] = nums[i] when 2 <= 2 * i <= n
• nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n

Return the maximum integer in the array nums​​​.

Example 1:

Input: n = 7

Output: 3

Explanation: According to the given rules:

nums[0] = 0
nums[1] = 1
nums[(1 * 2) = 2] = nums[1] = 1
nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
nums[(2 * 2) = 4] = nums[2] = 1
nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
nums[(3 * 2) = 6] = nums[3] = 2
nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3

Hence, nums = [0,1,1,2,1,3,2,3], and the maximum is max(0,1,1,2,1,3,2,3) = 3.

Example 2:

Input: n = 2

Output: 1

Explanation: According to the given rules, nums = [0,1,1]. The maximum is max(0,1,1) = 1.

Example 3:

Input: n = 3

Output: 2

Explanation: According to the given rules, nums = [0,1,1,2]. The maximum is max(0,1,1,2) = 2.

Constraints:

• 0 <= n <= 100

题目大意

给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：

• nums[0] = 0
• nums[1] = 1
• 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
• 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]

返回生成数组 nums 中的 最大 值。

示例 1：

输入： n = 7

输出： 3

解释： 根据规则：

nums[0] = 0
nums[1] = 1
nums[(1 * 2) = 2] = nums[1] = 1
nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
nums[(2 * 2) = 4] = nums[2] = 1
nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
nums[(3 * 2) = 6] = nums[3] = 2
nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3

因此，nums = [0,1,1,2,1,3,2,3]，最大值 3

示例 2：

输入： n = 2

输出： 1

解释： 根据规则，nums[0]、nums[1] 和 nums[2] 之中的最大值是 1

示例 3：

输入： n = 3

输出： 2

解释： 根据规则，nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2

提示：

• 0 <= n <= 100

解题思路

1. 特殊情况处理：

   • 如果 n == 0，返回 0。
   • 如果 n == 1，返回 1。

2. 数组初始化：

   • 创建一个长度为 n + 1 的数组 nums，初始赋值为 0。
   • 设置 nums[0] = 0，nums[1] = 1。

3. 动态生成数组：

   • 从索引 2 开始，依次计算 nums[i] 的值：
     • 如果 i 是偶数，nums[i] = nums[i / 2]。
     • 如果 i 是奇数，nums[i] = nums[(i - 1) / 2] + nums[(i - 1) / 2 + 1]。
   • 在计算过程中，更新最大值 max。

4. 返回结果：

   • 遍历完成后，返回 max。

复杂度分析

• 时间复杂度：O(n)，遍历从 2 到 n，计算每个元素的值。
• 空间复杂度：O(n)，使用了一个长度为 n + 1 的数组 nums。

代码

/**
 * @param {number} n
 * @return {number}
 */
var getMaximumGenerated = function (n) {
	if (n == 0) return 0;
	if (n == 1) return 1;

	let max = 0;
	const nums = new Array(n + 1);
	nums[0] = 0;
	nums[1] = 1;
	for (let i = 2; i <= n; i++) {
		if (i % 2 == 0) {
			nums[i] = nums[i / 2];
		} else {
			nums[i] = nums[(i - 1) / 2] + nums[(i - 1) / 2 + 1];
		}
		max = Math.max(max, nums[i]);
	}
	return max;
};

相关题目

题号	标题	题解	标签	难度	力扣
2789	合并后数组中的最大元素		贪心 数组	🟠	🀄️ 🔗