2736-最大和查询

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

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

对于第 i 个查询，在所有满足 nums1[j] >= xi 且 nums2[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] >= 1 。nums1[j] + nums2[j] 等于 6 ，可以证明 6 是可以获得的最大值。
对于第 2 个查询：xi = 1 且 yi = 3 ，可以选择下标 j = 2 ，此时 nums1[j] >= 1 且 nums2[j] >= 3 。nums1[j] + nums2[j] 等于 10 ，可以证明 10 是可以获得的最大值。
对于第 3 个查询：xi = 2 且 yi = 5 ，可以选择下标 j = 3 ，此时 nums1[j] >= 2 且 nums2[j] >= 5 。nums1[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

视频讲解

见个人主页。

思路

为方便处理，可以先把 nums}_1 和询问中的 x_i 排序。

这样就可以把重心放在 nums}_2[j] 与 y_i 的大小关系上。

我们可以按照 x_i 从大到小、nums}_1[j] 从大到小的顺序处理，同时增量地维护满足 nums}_1[j]\ge x_i 的 nums}_2[j]。

如何维护？分类讨论：

  • 如果 nums}_2[j] 比之前遍历过的 nums}_2[j’] 还要小，那么由于 nums}_1[j] 是从大到小处理的，所以 nums}_1[j]+\textit{nums}_2[j] 也比之前遍历过的 nums}_1[j’]+\textit{nums}_2[j’] 要小。那么在回答 \le \textit{nums}_2[j] 的 y_i 时，最大值不可能是 nums}_1[j]+\textit{nums}_2[j]，所以无需考虑这样的 nums}_2[j]。（这种单调性启发我们用单调栈来维护。）
  • 如果是相等，那么同理，无需考虑。
  • 如果是大于，那么就可以入栈。在入栈前还要去掉一些无效数据：
    • 如果 nums}_1[j]+\textit{nums}_2[j] 不低于栈顶的 nums}_1[j’]+\textit{nums}_2[j’]，那么可以弹出栈顶。因为更大的 nums}_2[j] 更能满足 \ge y_i 的要求，栈顶的 nums}_1[j’]+\textit{nums}_2[j’] 在后续的询问中，永远不会是最大值。
    • 代码实现时，可以直接比较 nums}_1[j]+\textit{nums}_2[j] 与栈顶的值，这是因为如果这一条件成立，由于 nums}_1[j] 是从大到小处理的，nums}_1[j]+\textit{nums}_2[j] 能比栈顶的大，说明 nums}_2[j] 必然不低于栈顶的 nums}_2[j’]。

这样我们会得到一个从栈底到栈顶，nums}_2[j] 递增，nums}_1[j]+\textit{nums}_2[j] 递减的单调栈。

最后在单调栈中二分 \ge y_i 的最小的 nums}_2[j]，对应的 nums}_1[j]+\textit{nums}_2[j] 就是最大的。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        ans = [-1] * len(queries)
        st = []
        a = sorted((a, b) for a, b in zip(nums1, nums2))
        i = len(a) - 1
        for qid, (x, y) in sorted(enumerate(queries), key=lambda p: -p[1][0]):
            while i >= 0 and a[i][0] >= x:
                ax, ay = a[i]
                while st and st[-1][1] <= ax + ay:  # ay >= st[-1][0]
                    st.pop()
                if not st or st[-1][0] < ay:
                    st.append((ay, ax + ay))
                i -= 1
            j = bisect_left(st, (y,))
            if j < len(st):
                ans[qid] = st[j][1]
        return ans
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func maximumSumQueries(nums1, nums2 []int, queries [][]int) (ans []int) {
	type pair struct{ x, y int }
	a := make([]pair, len(nums1))
	for i, x := range nums1 {
		a[i] = pair{x, nums2[i]}
	}
	sort.Slice(a, func(i, j int) bool { return a[i].x < a[j].x })
	for i := range queries {
		queries[i] = append(queries[i], i)
	}
	sort.Slice(queries, func(i, j int) bool { return queries[i][0] > queries[j][0] })

	ans = make([]int, len(queries))
	st := []pair{}
	i := len(a) - 1
	for _, q := range queries {
		for i >= 0 && a[i].x >= q[0] {
			for len(st) > 0 && st[len(st)-1].y <= a[i].x+a[i].y {
				st = st[:len(st)-1] // a[i].y >= st[len(st)-1].x
			}
			if len(st) == 0 || st[len(st)-1].x < a[i].y {
				st = append(st, pair{a[i].y, a[i].x + a[i].y})
			}
			i--
		}
		j := sort.Search(len(st), func(i int) bool { return st[i].x >= q[1] })
		if j < len(st) {
			ans[q[2]] = st[j].y
		} else {
			ans[q[2]] = -1
		}
	}
	return ans
}

复杂度分析

  • 时间复杂度：\mathcal{O}(n + q\log n)，其中 n 为 nums}_1 的长度，q 为 queries 的长度。
  • 空间复杂度：\mathcal{O}(n)。返回值不计。
 Comments
On this page
2736-最大和查询
  1. 视频讲解
  2. 思路