每一个查询的最大美丽值

给你一个二维整数数组items，其中items[i] = [pricei, beautyi]分别表示每一个物品的 价格 和 美丽值 。
同时给你一个下标从0开始的整数数组queries。对于每个查询queries[j]，你想求出价格小于等于queries[j]的物品中，最大的美丽值是多少。如果不存在符合条件的物品，那么查询的结果为0。
请你返回一个长度与queries相同的数组answer，其中answer[j]是第j个查询的答案。

离线算法 + 双指针

离线算法：将queries进行排序，通过改变回答询问的顺序，使得我们可以结合双指针来解决问题。
如果queries已经从小到大排好序了，那么就很好求解，使用双指针即可。但是queries是乱序的，返回值需要按照queries的顺序返回，我们可以额外创建一个数组idx，记录queries的下标，然后对idx按照queries[idx]的值进行从小到大的排序，遍历idx数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
    items.sort(key=lambda item:item[0])
    idx = sorted(range(len(queries)), key=lambda i:queries[i])

    ans = [0] * len(queries)
    j = 0
    beautify = 0
    for i in idx:
        q = queries[i]
        while j < len(items) and items[j][0] <= q:
            beautify = max(beautify, items[j][1])
            j += 1
        
        ans[i] = beautify

    return ans

在线算法 + 二分查找

  1. 先对items进行排序
  2. 然后每个items[i]的美丽值变为从items[0]到items[i]的美丽值的最大值
  3. 然后遍历queries，对于每一个查询，我们可以使用二分查找找到最后一个价格小于等于queries[j]的物品，该物品的美丽值就是我们要求的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
    n = len(queries)
    ans = [0] * n
    items.sort(key=lambda item : item[0])
    beautify = 0
    for i in range(len(items)):
        beautify = max(beautify, items[i][1])
        items[i][1] = beautify
    
    col = []
    for x,y in items:
        col.append(x)

    for i in range(n):
        x = bisect.bisect(col, queries[i])
        if x == 0:
            ans[i] = 0
            continue
        ans[i] = items[x-1][1]

    return ans