What is the main pattern used in Maximum Sum Queries?

The key pattern is binary search over the valid answer space combined with pre-sorted arrays for efficient query handling.

How do I handle queries that have no valid indices?

Return -1 for any query where no index j satisfies both nums1[j] >= xi and nums2[j] >= yi.

Why use a segment tree or monotonic stack?

These structures allow efficient retrieval of the maximum nums2[j] for the filtered nums1[j] indices without scanning all elements.

Can this approach handle large arrays and many queries?

Yes, sorting and using binary search plus segment trees reduce time complexity to O(n log n + q log n), suitable for n and q up to 10^5.

Do queries need to be processed in input order?

No, they can be sorted by xi descending for efficient processing but answers must be returned in the original query order.

#2736

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

最大和查询

给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，另给你一个下标从 1 开始的二维数组 queries ，其中 queries[i] = [x i , y i ] 。对于第 i 个查询，在所有满足 nums1[j] >= x i 且 nums2[j] >= y i 的…

数组二分查找栈树状数组线段树

题目描述

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

对于第 i 个查询，在所有满足 nums1[j] >= x_i 且 nums2[j] >= y_i 的下标 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 个查询：x_i = 4 且 y_i = 1 ，可以选择下标 j = 0 ，此时 nums1[j] >= 4 且 nums2[j] >= 1 。nums1[j] + nums2[j] 等于 6 ，可以证明 6 是可以获得的最大值。
对于第 2 个查询：x_i = 1 且 y_i = 3 ，可以选择下标 j = 2 ，此时 nums1[j] >= 1 且 nums2[j] >= 3 。nums1[j] + nums2[j] 等于 10 ，可以证明 10 是可以获得的最大值。
对于第 3 个查询：x_i = 2 且 y_i = 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]
解释：示例中的查询 x_i = 3 且 y_i = 3 。对于每个下标 j ，都只满足 nums1[j] < x_i 或者 nums2[j] < y_i 。因此，不存在答案。

提示：

nums1.length == nums2.length
n == nums1.length
1 <= n <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁹
1 <= queries.length <= 10⁵
queries[i].length == 2
x_i == queries[i][1]
y_i == queries[i][2]
1 <= x_i, y_i <= 10⁹

lightbulb

解题思路

方法一：树状数组

本题属于二维偏序问题。

二维偏序是这样一类问题：给定若干个点对 $(a_1, b_1)$ , $(a_2, b_2)$ , $\cdots$ , $(a_n, b_n)$ ，并定义某种偏序关系，现在给定点 $(a_i, b_i)$ ，求满足偏序关系的点对 $(a_j, b_j)$ 中的数量/最值。即：

\left(a_{j}, b_{j}\right) \prec\left(a_{i}, b_{i}\right) \stackrel{\text { def }}{=} a_{j} \lesseqgtr a_{i} \text { and } b_{j} \lesseqgtr b_{i}

二维偏序的一般解决方法是排序一维，用数据结构处理第二维（这种数据结构一般是树状数组）。

对于本题，我们可以创建一个数组 $nums$ ，其中 $nums[i]=(nums_1[i], nums_2[i])$ ，然后对 $nums$ 按照 $nums_1$ 从大到小的顺序排序，将查询 $queries$ 也按照 $x$ 从大到小的顺序排序。

接下来，遍历每个查询 $queries[i] = (x, y)$ ，对于当前查询，我们循环将 $nums$ 中所有大于等于 $x$ 的元素的 $nums_2$ 的值插入到树状数组中，树状数组维护的是离散化后的 $nums_2$ 的区间中 $nums_1 + nums_2$ 的最大值。那么我们只需要在树状数组中查询大于等于离散化后的 $y$ 区间对应的最大值即可。注意，由于树状数组维护的是前缀最大值，所以我们在实现上，可以将 $nums_2$ 反序插入到树状数组中。

时间复杂度 $O((n + m) \times \log n + m \times \log m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 是数组 $nums$ 的长度，而 $m$ 是数组 $queries$ 的长度。

相似题目：

2940. 找到 Alice 和 Bob 可以相遇的建筑

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

35

36

37

38

39

40

class BinaryIndexedTree:
    __slots__ = ["n", "c"]

    def __init__(self, n: int):
        self.n = n
        self.c = [-1] * (n + 1)

    def update(self, x: int, v: int):
        while x <= self.n:
            self.c[x] = max(self.c[x], v)
            x += x & -x

    def query(self, x: int) -> int:
        mx = -1
        while x:
            mx = max(mx, self.c[x])
            x -= x & -x
        return mx


class Solution:
    def maximumSumQueries(
        self, nums1: List[int], nums2: List[int], queries: List[List[int]]
    ) -> List[int]:
        nums = sorted(zip(nums1, nums2), key=lambda x: -x[0])
        nums2.sort()
        n, m = len(nums1), len(queries)
        ans = [-1] * m
        j = 0
        tree = BinaryIndexedTree(n)
        for i in sorted(range(m), key=lambda i: -queries[i][0]):
            x, y = queries[i]
            while j < n and nums[j][0] >= x:
                k = n - bisect_left(nums2, nums[j][1])
                tree.update(k, nums[j][0] + nums[j][1])
                j += 1
            k = n - bisect_left(nums2, y)
            ans[i] = tree.query(k)
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on sorting arrays and queries O(n log n + q log n) and segment tree updates, while space complexity depends on storing the preprocessed pairs and segment tree structures.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Sorting pairs and queries indicates efficient precomputation.
question_mark
Binary search over nums1 for each query shows pattern recognition of valid answer space.
question_mark
Using segment tree or monotonic stack shows candidate max sum tracking skill.

warning

常见陷阱

外企场景

error
Not indexing queries before sorting can misalign answers.
error
Scanning all elements for each query leads to TLE on large inputs.
error
Forgetting to handle the -1 case when no elements satisfy the constraints.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute minimum sum under similar constraints instead of maximum.
arrow_right_alt
Extend to 3D arrays or additional dimensions with threshold constraints.
arrow_right_alt
Allow updates to nums1 or nums2 between queries and recompute efficiently.

help

常见问题

外企场景

继续练习

#2940 找到 Alice 和 Bob 可以相遇的建筑 #2659 将数组清空 #2454 下一个更大元素 IV