调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

给你两个长度为 n 、下标从 0 开始的整数数组 nums1nums2 ,另给你一个下标从 1 开始的二维数组 queries ,其中 queries[i] = [xi, yi]

对于第 i 个查询,在所有满足 nums1[j] >= xinums2[j] >= yi 的下标 j (0 <= j < n) 中,找出 nums1[j] + nums2[j]最大值 ,如果不存在满足条件的 j 则返回 -1

返回数组 answer其中 answer[i] 是第 i 个查询的答案。

 

示例 1:

输入:nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]
输出:[6,10,7]
解释:
对于第 1 个查询:xi = 4 且 yi = 1 ,可以选择下标 j = 0 ,此时 nums1[j] >= 4 且 nums2[j] >= 1nums1[j] + nums2[j] 等于 6 ,可以证明 6 是可以获得的最大值。
对于第 2 个查询:xi = 1 且 yi = 3 ,可以选择下标 j = 2 ,此时 nums1[j] >= 1 且 nums2[j] >= 3nums1[j] + nums2[j] 等于 10 ,可以证明 10 是可以获得的最大值。
对于第 3 个查询:xi = 2 且 yi = 5 ,可以选择下标 j = 3 ,此时 nums1[j] >= 2 且 nums2[j] >= 5nums1[j] + nums2[j] 等于 7 ,可以证明 7 是可以获得的最大值。
因此,我们返回 [6,10,7]

示例 2:

输入:nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
输出:[9,9,9]
解释:对于这个示例,我们可以选择下标 j = 2 ,该下标可以满足每个查询的限制。

示例 3:

输入:nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]
输出:[-1]
解释:示例中的查询 xi = 3 且 yi = 3 。对于每个下标 j ,都只满足 nums1[j] < xi 或者 nums2[j] < yi 。因此,不存在答案。 

 

提示:

  • nums1.length == nums2.length 
  • n == nums1.length 
  • 1 <= n <= 105
  • 1 <= nums1[i], nums2[i] <= 109 
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • xi == queries[i][1]
  • yi == queries[i][2]
  • 1 <= xi, yi <= 109
通过次数
13.2K
提交次数
25.4K
通过率
52.1%


相关企业

提示 1
Sort (x, y) tuples and queries by x-coordinate descending. Don’t forget to index queries before sorting so that you can answer them in the correct order.

提示 2
Before answering a query (min_x, min_y), add all (x, y) pairs with x >= min_x to some data structure.

提示 3
Use a monotone descending map to store (y, x + y) pairs. A monotone map has ascending keys and descending values. When inserting a pair (y, x + y), remove all pairs (y', x' + y') with y' < y and x' + y' <= x + y.

提示 4
To find the insertion position use binary search (built-in in many languages).

提示 5
When querying for max (x + y) over y >= y', use binary search to find the first pair (y, x + y) with y >= y'. It will have the maximum value of x + y because the map has monotone descending values.


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
nums1 =
[4,3,1,2]
nums2 =
[2,4,9,5]
queries =
[[4,1],[1,3],[2,5]]
Source