最大和查询

标签: 栈 树状数组 线段树 数组 二分查找 排序 单调栈

难度: Hard

给你两个长度为 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

Submission

运行时间: 152 ms

内存: 64.5 MB

class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        # nums = sorted(zip(nums1, nums2), reverse = True)
        # sq = sorted(enumerate(queries), key = lambda x: x[1], reverse = True)
        # n = len(nums1)
        # q = len(queries)
        # res = [-1 for _ in range(q)]
        # j = 0
        # stack = []
        # for i, (x, y) in sq :
        #     while j < n and nums[j][0] >= x :
        #         s = sum(nums[j])
        #         while stack and stack[-1][1] <= s :
        #             stack.pop()
        #         if not stack or stack[-1][0] < nums[j][1] :
        #             stack.append([nums[j][1], s])
        #         j += 1
        #     k = bisect.bisect_left(stack, [y, 0])
        #     if k < len(stack) :
        #         res[i] = stack[k][1]
        # return res


        nums = sorted([(x + y, x, y) for x, y in zip(nums1, nums2)], reverse = True)
        res = []

        @cache
        def query(x, y) :
            for s, n1, n2 in nums :
                if s < x + y :
                    return -1
                if n1 >= x and n2 >= y :
                    return s
            return -1

        for x, y in queries :
            res.append(query(x, y))
        return res

Explain

这个题解首先将nums1和nums2的每个元素对应相加，并与原始值一同存储，然后对这个组合列表按照和的降序进行排序。对于每个查询，通过一个缓存的函数`query`来处理，该函数遍历排序后的列表，检查每个元素是否满足查询条件，返回满足条件的最大和或-1。由于列表是按和排序的，因此一旦和小于xi和yi的和，就可以直接返回-1，提高了效率。

时间复杂度: O(n log n + q * n)

空间复杂度: O(n + q)

class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        # 将nums1和nums2对应元素相加，并存储三元组(和，nums1元素，nums2元素)，按总和降序排序
        nums = sorted([(x + y, x, y) for x, y in zip(nums1, nums2)], reverse = True)
        res = []

        @cache
        def query(x, y) :
            # 遍历排序后的列表，查找满足条件的最大和
            for s, n1, n2 in nums :
                # 如果当前和小于x+y，直接返回-1
                if s < x + y :
                    return -1
                # 检查是否满足查询条件
                if n1 >= x and n2 >= y :
                    return s
            return -1

        # 对每个查询调用缓存的查询函数
        for x, y in queries :
            res.append(query(x, y))
        return res

Explore

将nums1和nums2的元素相加得到的和可以直接代表两个数组中相应位置的元素的总体贡献。通过对这些和进行排序，我们可以快速定位到可能的最大和。当处理查询时，排序后的数组可以让我们从最大可能和开始检查，这样一旦找到第一个满足条件的和，即可确定为最大和。这种方式避免了从小到大逐个检查每个组合的低效率，尤其是在和较大或对和的要求较高的情况下，可以显著减少必要的比较次数。

在题解中，使用了Python的装饰器`@cache`来缓存`query`函数的结果。这意味着每一次对于相同的x和y值的查询结果会被存储起来，当再次遇到相同的查询时，可以直接从缓存中获取答案而不需要重新计算。这种方法在处理多个重复查询时非常有效，因为它避免了对于同一查询条件的重复计算，从而提高了算法的整体效率。

这种逻辑是基于数组已经按照和的降序排列的事实。如果在遍历过程中遇到一个和小于查询的x+y，由于后续的和只会更小，因此不可能存在一个更大的和满足查询条件。这使得算法可以在确认无法找到满足条件的和时立即停止，从而节省时间，避免无效的计算。

这个问题的答案取决于不满足条件的具体情况。如果当前元素的和已经小于查询的x+y，则由于列表是降序的，后续的所有元素的和都会更小，因此不可能满足条件。但如果当前元素的和足够大，但是其nums1或nums2的值不满足x或y的要求，则无法立即断定后续元素也不满足条件，因为可能存在后续的其他元素虽然和较小，但具体的nums1或nums2的值可能满足条件。