最大和查询
难度:
标签:
题目描述
You are given two 0-indexed integer arrays nums1 and nums2, each of length n, and a 1-indexed 2D array queries where queries[i] = [xi, yi].
For the ith query, find the maximum value of nums1[j] + nums2[j] among all indices j (0 <= j < n), where nums1[j] >= xi and nums2[j] >= yi, or -1 if there is no j satisfying the constraints.
Return an array answer where answer[i] is the answer to the ith query.
Example 1:
Input: nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]] Output: [6,10,7] Explanation: For the 1st queryxi = 4andyi = 1, we can select indexj = 0sincenums1[j] >= 4andnums2[j] >= 1. The sumnums1[j] + nums2[j]is 6, and we can show that 6 is the maximum we can obtain. For the 2nd queryxi = 1andyi = 3, we can select indexj = 2sincenums1[j] >= 1andnums2[j] >= 3. The sumnums1[j] + nums2[j]is 10, and we can show that 10 is the maximum we can obtain. For the 3rd queryxi = 2andyi = 5, we can select indexj = 3sincenums1[j] >= 2andnums2[j] >= 5. The sumnums1[j] + nums2[j]is 7, and we can show that 7 is the maximum we can obtain. Therefore, we return[6,10,7].
Example 2:
Input: nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
Output: [9,9,9]
Explanation: For this example, we can use index j = 2 for all the queries since it satisfies the constraints for each query.
Example 3:
Input: nums1 = [2,1], nums2 = [2,3], queries = [[3,3]] Output: [-1] Explanation: There is one query in this example withxi= 3 andyi= 3. For every index, j, either nums1[j] <xior nums2[j] <yi. Hence, there is no solution.
Constraints:
nums1.length == nums2.lengthn == nums1.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 1091 <= queries.length <= 105queries[i].length == 2xi == queries[i][1]yi == queries[i][2]1 <= xi, yi <= 109
代码结果
运行时间: 152 ms, 内存: 64.5 MB
/*
* 思路：
* 使用 Java Stream API 优化代码，实现同样的逻辑。
*/
import java.util.stream.IntStream;
public int[] maxSumQueries(int[] nums1, int[] nums2, int[][] queries) {
return IntStream.range(0, queries.length).map(i -> {
int x = queries[i][0];
int y = queries[i][1];
return IntStream.range(0, nums1.length)
.filter(j -> nums1[j] >= x && nums2[j] >= y)
.map(j -> nums1[j] + nums2[j])
.max()
.orElse(-1);
}).toArray();
}解释
方法:
这个题解首先将nums1和nums2的每个元素对应相加，并与原始值一同存储，然后对这个组合列表按照和的降序进行排序。对于每个查询，通过一个缓存的函数`query`来处理，该函数遍历排序后的列表，检查每个元素是否满足查询条件，返回满足条件的最大和或-1。由于列表是按和排序的，因此一旦和小于xi和yi的和，就可以直接返回-1，提高了效率。
时间复杂度:
O(n log n + q * n)
空间复杂度:
O(n + q)
代码细节讲解
🦆
在题解中，你是如何确定将nums1和nums2的元素对应相加后进行排序是一个有效的优化步骤？
▷🦆
题解中提到使用缓存来优化处理查询的步骤，具体是如何实现的？请解释这种方法如何减少计算重复度？
▷🦆
题解中提到一旦当前和小于查询的x+y就可以返回-1，这种提前停止的逻辑是基于什么假设或保证？
▷🦆
排序后的列表遍历检查是否满足查询条件时，如果不满足条件直接返回-1，这是否意味着排序后的列表中所有后续的元素都不会满足条件？请解释原因。
▷