LeetCode 题解工作台
获取生成数组中的最大值
给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ： nums[0] = 0 nums[1] = 1 当 2 时， nums[2 * i] = nums[i] 当 2 时， nums[2 * i + 1] = nums[i] + nums[i + 1] 返回生成数组 num…
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·模拟
答案摘要
我们先判断 的值，如果 $n < 2$，则直接返回 。 否则，我们创建一个长度为 $n + 1$ 的数组 ，并初始化 $nums[0] = 0$ 以及 $nums[1] = 1$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·模拟 题型思路
题目描述
给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
nums[0] = 0nums[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
解题思路
方法一：模拟
我们先判断 的值，如果 ，则直接返回 。
否则，我们创建一个长度为 的数组 ，并初始化 以及 。
然后从下标 开始遍历，如果当前下标 为偶数，则 ，否则 。
最后返回数组 中的最大值即可。
时间复杂度 ，空间复杂度 。其中 为给定的整数。
class Solution:
def getMaximumGenerated(self, n: int) -> int:
if n < 2:
return n
nums = [0] * (n + 1)
nums[1] = 1
for i in range(2, n + 1):
nums[i] = nums[i >> 1] if i % 2 == 0 else nums[i >> 1] + nums[(i >> 1) + 1]
return max(nums)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each index from 0 to n is computed once. Space complexity is O(n) for storing the array. Tracking the maximum adds no extra asymptotic cost. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may ask you to explain how you handle even and odd indices differently in the recurrence.
- question_mark
Expect a question about why linear simulation is sufficient versus using mathematical formulas.
- question_mark
They might probe whether you can optimize space or track the maximum without storing the full array.
常见陷阱
外企场景- error
Forgetting to handle n = 0 or n = 1 correctly can lead to index errors.
- error
Incorrectly applying nums[2 * i + 1] = nums[i] + nums[i + 1] may yield wrong values.
- error
Not updating the maximum while generating the array can require an extra traversal.
进阶变体
外企场景- arrow_right_alt
Return the index of the maximum instead of the value to test tracking during simulation.
- arrow_right_alt
Modify the recurrence to include multipliers and track how that changes the maximum.
- arrow_right_alt
Generate the array recursively instead of iteratively and compare time and space efficiency.