最大得分
难度:
标签:
题目描述
你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。
一条 合法路径 定义如下：
- 选择数组
nums1或者nums2开始遍历（从下标 0 处开始）。 - 从左到右遍历当前数组。
- 如果你遇到了
nums1和nums2中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。
得分 定义为合法路径中不同数字的和。
请你返回 所有可能 合法路径 中的最大得分。由于答案可能很大，请你将它对 10^9 + 7 取余后返回。
示例 1：
输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9] 输出：30 解释：合法路径包括： [2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（从 nums1 开始遍历） [4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10] （从 nums2 开始遍历） 最大得分为上图中的绿色路径 [2,4,6,8,10] 。
示例 2：
输入：nums1 = [1,3,5,7,9], nums2 = [3,5,100] 输出：109 解释：最大得分由路径 [1,3,5,100] 得到。
示例 3：
输入：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10] 输出：40 解释：nums1 和 nums2 之间无相同数字。 最大得分由路径[6,7,8,9,10]得到。
提示：
1 <= nums1.length, nums2.length <= 1051 <= nums1[i], nums2[i] <= 107nums1和nums2都是严格递增的数组。
代码结果
运行时间: 65 ms, 内存: 25.1 MB
/*
* 思路：
* 1. 使用流操作来简化代码逻辑。
* 2. 使用 IntStream.range 对 nums1 和 nums2 进行遍历并计算路径和。
* 3. 在遇到相同元素时，选择最大路径和继续前进。
* 4. 最后取最大值并对结果取余。
*/
import java.util.*;
import java.util.stream.IntStream;
public class MaxScoreStream {
public int maxSum(int[] nums1, int[] nums2) {
final int MOD = 1_000_000_007;
long sum1 = 0, sum2 = 0;
long result = IntStream.range(0, Math.min(nums1.length, nums2.length)).mapToLong(i -> {
if (nums1[i] < nums2[i]) {
sum1 += nums1[i];
} else if (nums1[i] > nums2[i]) {
sum2 += nums2[i];
} else { // nums1[i] == nums2[i]
long maxSum = Math.max(sum1, sum2) + nums1[i];
sum1 = sum2 = 0;
return maxSum;
}
return 0;
}).sum();
result += Math.max(sum1, sum2);
return (int)(result % MOD);
}
}解释
方法:
此题解使用双指针技术遍历两个有序数组nums1和nums2，同时维护两个累加器best1和best2来记录从每个数组开始的可能的最大分数。遍历过程中，根据当前指针指向的元素大小，增加较小值到对应的累加器。当两数组在某位置的元素相等时，可以从一个数组切换到另一个，因此更新best1和best2为这两者的最大值加当前共同元素。这样保证了在遇到共同元素时，选择到目前为止可能得到的最大分数继续累积。遍历完两数组后，比较两个累加器的值，取最大值作为结果。由于结果可能很大，最终对10^9 + 7取模。
时间复杂度:
O(m + n)
空间复杂度:
O(1)
代码细节讲解
🦆
在双指针技术中，如何确保在遍历过程中不会遗漏掉可能的最大分数路径？
▷🦆
当两数组元素相等时，更新best1和best2为两者的最大值加当前共同元素的原理是什么？为什么不是简单地累加当前元素？
▷🦆
算法中的while循环处理剩余元素时，为什么可以直接累加剩余元素到best1或best2，而不需要继续比较两个数组的元素？
▷🦆
该题解如何处理两个数组长度不等的情况，特别是当一个数组早早遍历完成，而另一个数组还有多个元素未处理时？
▷