【Leetcode 每日一题 - 补卡】2070. 每一个查询的最大美丽值

问题背景

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

数据约束

• $1\le items.length,queries.length\le 10^5$
• $items[i].length=2$
• $1\le pric{e}_i,beaut{y}_i,queries[j]\le 10^9$

解题过程

将 $items$ 数组根据 $price$ 从小到大排序，然后将每个位置上的美丽值更新为前缀最大值，这时要求的答案就是最后一个满足 $pric{e}_i\le query$ 的前缀最大值，可以用二分。

解题过程

class Solution {public int[] maximumBeauty(int[][] items, int[] queries) {Arrays.sort(items, (o1, o2) -> o1[0] - o2[0]);for (int i = 1; i < items.length; i++) {items[i][1] = Math.max(items[i][1], items[i - 1][1]);}for (int i = 0; i < queries.length; i++) {int j = binarySearch(items, queries[i] + 1);queries[i] = j > 0 ? items[j - 1][1] : 0;}return queries;}private int binarySearch(int[][] items, int target) {int left = 0;int right = items.length;while (left < right) {int mid = left + ((right - left) >>> 1);if (items[mid][0] < target) {left = mid + 1;} else {right = mid;}}return left;}
}