Day33力扣打卡

打卡记录

最大和查询（排序+单调栈上二分）

链接

大佬的题解

class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        ans = [-1] * len(queries)
        a = sorted(((a, b) for a, b in zip(nums1, nums2)), key=lambda p: -p[0])
        j = 0
        st = []
        for i, (x, y) in sorted(enumerate(queries), key=lambda p: -p[1][0]):
            while j < len(a) and a[j][0] >= x:  # 下面只需关心 ay (a[j][1])
                ax, ay = a[j]
                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))
                j += 1
            p = bisect_left(st, (y,))
            if p < len(st):
                ans[i] = st[p][1]
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18