杭州做网站工作室网页代码大全
问题背景
给你一个二维整数数组 i t e m s items items，其中 i t e m s [ i ] = [ p r i c e i , b e a u t y i ] items[i] = [price_i, beauty_i] items[i]=[pricei,beautyi] 分别表示每一个物品的 价格 和 美丽值 。
同时给你一个下标从 0 0 0 开始的整数数组 q u e r i e s queries queries。对于每个查询 q u e r i e s [ j ] queries[j] queries[j]，你想求出价格小于等于 q u e r i e s [ j ] queries[j] queries[j] 的物品中，最大的美丽值 是多少。如果不存在符合条件的物品，那么查询的结果为 0 0 0。
请你返回一个长度与 q u e r i e s queries queries 相同的数组 a n s w e r answer answer，其中 a n s w e r [ j ] answer[j] answer[j] 是第 j j j 个查询的答案。
数据约束
- 1 ≤ i t e m s . l e n g t h , q u e r i e s . l e n g t h ≤ 1 0 5 1 \le items.length, queries.length \le 10 ^ 5 1≤items.length,queries.length≤105
- i t e m s [ i ] . l e n g t h = 2 items[i].length = 2 items[i].length=2
- 1 ≤ p r i c e i , b e a u t y i , q u e r i e s [ j ] ≤ 1 0 9 1 \le price_i, beauty_i, queries[j] \le 10 ^ 9 1≤pricei,beautyi,queries[j]≤109
解题过程
将 i t e m s items items 数组根据 p r i c e price price 从小到大排序，然后将每个位置上的美丽值更新为前缀最大值，这时要求的答案就是最后一个满足 p r i c e i ≤ q u e r y price_i \le query pricei≤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;}
}