Easy

题目描述

给你一个整数 n。一个长度为 n + 1 的从 0 开始索引的整数数组 nums 按以下方式生成：

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

返回数组 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]，最大值是 max(0,1,1,2,1,3,2,3) = 3。

示例 2：

输入：n = 2
输出：1
解释：根据规则，nums = [0,1,1]。最大值是 max(0,1,1) = 1。

示例 3：

输入：n = 3
输出：2
解释：根据规则，nums = [0,1,1,2]。最大值是 max(0,1,1,2) = 2。

提示：

  • 0 <= n <= 100

解题思路

这道题要求我们按照特定规则生成数组，然后找到数组中的最大值。

核心思路：

  1. 直接模拟数组生成过程。首先初始化数组的前两个元素：nums[0] = 0, nums[1] = 1（如果n >= 1）。

  2. 接下来按照题目给定的规则依次生成每个位置的值：

    • 对于偶数索引 2i：nums[2i] = nums[i]
    • 对于奇数索引 2i+1：nums[2i+1] = nums[i] + nums[i+1]

  3. 在生成过程中，同时维护一个变量记录遇到的最大值，避免最后再遍历整个数组。

边界情况处理：

  • 当 n = 0 时，数组只有一个元素 0，直接返回 0
  • 当 n >= 1 时，按照正常流程生成数组

算法优化： 虽然可以生成完整数组后再找最大值，但更高效的方法是在生成过程中实时更新最大值，这样可以节省额外的遍历时间。

时间复杂度为 O(n)，空间复杂度为 O(n)。由于 n 的范围很小（≤100），这个解法完全满足要求。

代码实现

class Solution {
public:
    int getMaximumGenerated(int n) {
        if (n == 0) return 0;
        
        vector<int> nums(n + 1);
        nums[0] = 0;
        nums[1] = 1;
        
        int maxVal = 1;
        
        for (int i = 1; i <= n / 2; i++) {
            if (2 * i <= n) {
                nums[2 * i] = nums[i];
                maxVal = max(maxVal, nums[2 * i]);
            }
            if (2 * i + 1 <= n) {
                nums[2 * i + 1] = nums[i] + nums[i + 1];
                maxVal = max(maxVal, nums[2 * i + 1]);
            }
        }
        
        return maxVal;
    }
};

class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n == 0:
            return 0
        
        nums = [0] * (n + 1)
        nums[0] = 0
        nums[1] = 1
        
        max_val = 1
        
        for i in range(1, n // 2 + 1):
            if 2 * i <= n:
                nums[2 * i] = nums[i]
                max_val = max(max_val, nums[2 * i])
            if 2 * i + 1 <= n:
                nums[2 * i + 1] = nums[i] + nums[i + 1]
                max_val = max(max_val, nums[2 * i + 1])
        
        return max_val

public class Solution {
    public int GetMaximumGenerated(int n) {
        if (n == 0) return 0;
        
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        
        int maxVal = 1;
        
        for (int i = 1; i <= n / 2; i++) {
            if (2 * i <= n) {
                nums[2 * i] = nums[i];
                maxVal = Math.Max(maxVal, nums[2 * i]);
            }
            if (2 * i + 1 <= n) {
                nums[2 * i + 1] = nums[i] + nums[i + 1];
                maxVal = Math.Max(maxVal, nums[2 * i + 1]);
            }
        }
        
        return maxVal;
    }
}

var getMaximumGenerated = function(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    let nums = new Array(n + 1);
    nums[0] = 0;
    nums[1] = 1;
    let max = 1;
    
    for (let i = 1; i <= n; i++) {
        if (2 * i <= n) {
            nums[2 * i] = nums[i];
            max = Math.max(max, nums[2 * i]);
        }
        if (2 * i + 1 <= n) {
            nums[2 * i + 1] = nums[i] + nums[i + 1];
            max = Math.max(max, nums[2 * i + 1]);
        }
    }
    
    return max;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)需要遍历生成数组中的每个元素
空间复杂度O(n)需要创建长度为 n+1 的数组存储生成的数值

相关题目