2736.最大和查询
链接:2736.最大和查询
难度: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 - python
- 编辑时间:2023-11-17
- 执行用时:340ms
- 内存消耗:56.66MB
- 编程语言:python
- 解法介绍:单调栈。
class Solution:
def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
n = len(nums1)
nums = [(nums1[i], nums2[i]) for i in range(n)]
nums.sort()
qn = len(queries)
qlist = [i for i in range(qn)]
qlist.sort(key = lambda i: queries[i])
stack = []
ans = [0] * qn
while qlist:
qidx = qlist.pop()
x, y = queries[qidx]
while nums and x <= nums[-1][0]:
xnum, ynum = nums.pop()
while stack and stack[-1][1] <= xnum + ynum:
stack.pop()
if not stack or stack[-1][0] < ynum:
stack.append((ynum, xnum + ynum))
idx = bisect_left(stack, (y, 0))
ans[qidx] = stack[idx][1] if idx < len(stack) else -1
return ans