Leetcode-每日一题-补卡2070.-每一个查询的最大美丽值
【Leetcode 每日一题 - 补卡】2070. 每一个查询的最大美丽值
问题背景
给你一个二维整数数组
i t e m s items
i
t
e
m
s ，其中
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]
i
t
e
m
s
[
i
]
=
[
p
r
i
c
e
i
,
b
e
a
u
t
y
i
] 分别表示每一个物品的 价格 和 美丽值 。
同时给你一个下标从
0 0
0 开始的整数数组
q u e r i e s queries
q
u
er
i
es 。对于每个查询
q u e r i e s [ j ] queries[j]
q
u
er
i
es
[
j
] ，你想求出价格小于等于
q u e r i e s [ j ] queries[j]
q
u
er
i
es
[
j
] 的物品中，最大的美丽值 是多少。如果不存在符合条件的物品，那么查询的结果为
0 0
0 。
请你返回一个长度与
q u e r i e s queries
q
u
er
i
es 相同的数组
a n s w e r answer
an
s
w
er ，其中
a n s w e r [ j ] answer[j]
an
s
w
er
[
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
≤
i
t
e
m
s
.
l
e
n
g
t
h
,
q
u
er
i
es
.
l
e
n
g
t
h
≤
1
0
5
i t e m s [ i ] . l e n g t h
2 items[i].length = 2
i
t
e
m
s
[
i
]
.
l
e
n
g
t
h
=
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
≤
p
r
i
c
e
i
,
b
e
a
u
t
y
i
,
q
u
er
i
es
[
j
]
≤
1
0
9
解题过程
将
i t e m s items
i
t
e
m
s 数组根据
p r i c e price
p
r
i
ce 从小到大排序，然后将每个位置上的美丽值更新为前缀最大值，这时要求的答案就是最后一个满足
p r i c e i ≤ q u e r y price_i \le query
p
r
i
c
e
i
≤
q
u
ery 的前缀最大值，可以用二分。
解题过程
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;
}
}