leetcode
leetcode 1501 ~ 1550
获取生成数组中的最大值

获取生成数组中的最大值

难度:

标签:

题目描述

代码结果

运行时间: 16 ms, 内存: 16.1 MB


/*
 * Solution approach using Java Streams for generating the array and finding the maximum value:
 * 1. Initialize an array of length n+1 with all zeros.
 * 2. Set the first two values: nums[0] = 0 and nums[1] = 1.
 * 3. Use IntStream to fill the array based on the given rules.
 * 4. Use IntStream to find and return the maximum value in the array.
 */
import java.util.stream.IntStream;
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;
        IntStream.range(2, n + 1).forEach(i -> {
            if (i % 2 == 0) {
                nums[i] = nums[i / 2];
            } else {
                nums[i] = nums[i / 2] + nums[i / 2 + 1];
            }
        });
        return IntStream.of(nums).max().orElse(0);
    }
}

解释

方法:

此题解使用动态规划的方法来生成数组 nums,并实时跟踪最大值。数组 dp 初始化为长度 n+1 的全0数组,其中 dp[0]=0 和 dp[1]=1 是初始条件。接着,从 i=2 开始迭代至 n,根据 i 的奇偶性使用不同的规则更新 dp[i]。如果 i 是偶数,根据规则 dp[i] = dp[i//2];如果是奇数,则 dp[i] = dp[(i+1)//2] + dp[(i-1)//2]。在每次更新 dp[i] 之后,还会更新 Maxdp 来保持记录数组中的最大值。最终,返回 Maxdp 作为结果。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在初始化阶段,为什么选择将dp数组的长度设置为n+1而不是n?
在初始化阶段,dp数组的长度被设置为n+1是为了保证数组能够容纳从0到n所有的索引。由于dp数组是用来存储每个索引对应的计算值,如果设置长度为n,那么索引n将会越界,因为数组索引是从0开始的。因此,为了方便直接使用索引值作为数组的索引,并避免越界错误,选择将dp数组的长度设置为n+1。
🦆
题解中提到的动态规划在更新dp[i]时,为什么i的奇偶性会决定使用不同的更新规则?
题解中使用不同的更新规则是基于动态规划的设计,它模拟了一个特定的数列生成规则。当i是偶数时,dp[i]的值是由dp[i/2]直接得来,这是因为偶数可以直接除以2而不改变整数性质。而当i是奇数时,dp[i]的值是dp[(i+1)/2]和dp[(i-1)/2]的和,这模拟了在奇数位置上的值由其相邻的偶数位置的值组合而成。这种设计是为了根据i的属性(奇偶性)有效地构造出整个数组。
🦆
解法中使用Maxdp变量来实时记录最大值,这种方法与在最后遍历dp数组寻找最大值相比,有什么优势或劣势?
使用Maxdp变量来实时记录最大值的优势在于效率。通过这种方式,我们可以在构建数组的同时跟踪最大值,避免了构建完整个数组后还需要再次遍历整个数组来找出最大值,从而减少了时间复杂度。然而,这种方法的劣势可能在于需要额外的操作来更新Maxdp,这在某些情况下可能稍微增加了每次迭代的计算负担。但总的来说,这种方法更适合实时或一次性处理的场景,可以有效提高总体效率。
🦆
在题解说明中,对于边界条件n小于2时直接返回n的处理方式,这是否适用于所有小于2的n值,包括负数或非整数?
在题解说明中,对于边界条件直接返回n的处理方式主要适用于n为0或1的情况,因为在这个特定问题中,dp数组的定义和逻辑是基于非负整数的序列。如果n是负数或非整数,这种处理方法在逻辑上并不适合,因为题目设定和dp数组的构建都是针对非负整数序列的。因此,对于负数或非整数的输入,应该考虑抛出错误或返回不合适的输入提示,而不是简单地返回n。

相关问题