目标
给你一个二维整数数组 items ，其中 items[i] = [pricei, beautyi] 分别表示每一个物品的 价格 和 美丽值 。
同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中，最大的美丽值 是多少。如果不存在符合条件的物品，那么查询的结果为 0 。
请你返回一个长度与 queries 相同的数组 answer，其中 answer[j]是第 j 个查询的答案。
示例 1：
输入：items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
输出：[2,4,5,5,6,6]
解释：
- queries[0]=1 ，[1,2] 是唯一价格 <= 1 的物品。所以这个查询的答案为 2 。
- queries[1]=2 ，符合条件的物品有 [1,2] 和 [2,4] 。
它们中的最大美丽值为 4 。
- queries[2]=3 和 queries[3]=4 ，符合条件的物品都为 [1,2] ，[3,2] ，[2,4] 和 [3,5] 。
它们中的最大美丽值为 5 。
- queries[4]=5 和 queries[5]=6 ，所有物品都符合条件。
所以，答案为所有物品中的最大美丽值，为 6 。示例 2：
输入：items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
输出：[4]
解释：
每个物品的价格均为 1 ，所以我们选择最大美丽值 4 。
注意，多个物品可能有相同的价格和美丽值。示例 3：
输入：items = [[10,1000]], queries = [5]
输出：[0]
解释：
没有物品的价格小于等于 5 ，所以没有物品可以选择。
因此，查询的结果为 0 。说明：
- 1 <= items.length, queries.length <= 10^5
- items[i].length == 2
- 1 <= pricei, beautyi, queries[j] <= 10^9
思路
有一个二维数组 items，其元素 items[i] = [pricei, beautyi] 表示 item 的价格与美丽值。有一个查询数组，每一次查询的目标是找出价格小于等于 queries[i] 的物品中的最大美丽值。
为了求得答案，需要知道小于 queries[i] 都有哪些物品，然后从中找出最大美丽值。
先将 items 按照价格从小到大排序，二分查找 queries[i] 的上界下标 end。剩下的问题是找出 [0, end] 范围内的最大美丽值，这些值是固定的，可以预处理。
代码
/**
* @date 2025-03-09 22:44
*/
public class MaximumBeauty2070 {
public int[] maximumBeauty(int[][] items, int[] queries) {
int n = items.length;
Arrays.sort(items, (a, b) -> a[0] - b[0]);
int[] maxBeauty = new int[n];
maxBeauty[0] = items[0][1];
for (int i = 1; i < n; i++) {
maxBeauty[i] = Math.max(maxBeauty[i - 1], items[i][1]);
}
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int upperbound = bs(queries[i], items);
if (upperbound >= 0 && upperbound < n) {
res[i] = maxBeauty[upperbound];
}
}
return res;
}
public int bs(int target, int[][] items) {
int n = items.length;
int left = 0, right = n - 1;
int mid = left + (right - left) / 2;
while (left <= right) {
if (items[mid][0] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
mid = left + (right - left) / 2;
}
return right;
}
}
性能
