class Solution {
public:
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
}
};
2070. 每一个查询的最大美丽值
给你一个二维整数数组 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 <= 105items[i].length == 21 <= pricei, beautyi, queries[j] <= 109原站题解
javascript 解法, 执行用时: 228 ms, 内存消耗: 77.3 MB, 提交时间: 2023-09-14 00:35:37
/**
* @param {number[][]} items
* @param {number[]} queries
* @return {number[]}
*/
var maximumBeauty = function(items, queries) {
items.sort((a,b) => a[0] - b[0]);
let res = queries.slice().fill(0);
let max = [];
let maxVal = -1;
for (let [a,b] of items) {
// price, beauty
maxVal = Math.max(maxVal, b);
max.push(maxVal);
}
for (let i=0; i<queries.length; i++) {
let l = 0, r = items.length - 1;
while (l < r) {
let m = Math.ceil((l + r)/2);
if (items[m][0] <= queries[i]) l = m;
else r = m - 1;
}
if (items[l][0] <= queries[i]) res[i] = max[l];
}
return res;
};
python3 解法, 执行用时: 252 ms, 内存消耗: 63.1 MB, 提交时间: 2023-09-14 00:35:27
class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
items.sort()
lst1, lst2 = zip(*items)
lst2 = list(accumulate(lst2, func = max, initial = 0))
return [lst2[bisect.bisect_right(lst1, q)] for q in queries]
java 解法, 执行用时: 45 ms, 内存消耗: 76.4 MB, 提交时间: 2023-09-14 00:34:55
class Solution {
public int[] maximumBeauty(int[][] items, int[] queries) {
int n = items.length;
int[] d = new int[n];
Arrays.sort(items, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]); //注意：这里价格相同时，美丽值降序
d[0] = items[0][1];
for (int i = 1; i < n; i++) {
d[i] = Math.max(d[i - 1], items[i][1]);
}
int[] res = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int l = 0, r = n - 1;
if (items[r][0] <= queries[i]) {
res[i] = d[r];
continue;
}
if (items[l][0] > queries[i]) continue;
while (l < r) {
int mid = l + (r - l) / 2;
if (items[mid][0] <= queries[i])
l = mid + 1;
else r = mid;
}
res[i] = d[l - 1];
}
return res;
}
}
cpp 解法, 执行用时: 380 ms, 内存消耗: 86.7 MB, 提交时间: 2023-09-14 00:34:34
class Solution {
public:
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
// 将物品按价格升序排序
sort(items.begin(), items.end(), [](auto&& item1, auto&& item2) {
return item1[0] < item2[0];
});
int n = items.size();
// 按定义修改美丽值
for (int i = 1; i < n; ++i){
items[i][1] = max(items[i][1], items[i-1][1]);
}
// 二分查找处理查询
auto query = [&](int q) -> int{
int l = 0, r = n;
while (l < r){
int mid = l + (r - l) / 2;
if (items[mid][0] > q){
r = mid;
}
else{
l = mid + 1;
}
}
if (l == 0){
// 此时所有物品价格均大于查询价格
return 0;
}
else{
// 返回小于等于查询价格的物品的最大美丽值
return items[l-1][1];
}
};
vector<int> res;
for (int q: queries){
res.push_back(query(q));
}
return res;
}
};
python3 解法, 执行用时: 424 ms, 内存消耗: 61.5 MB, 提交时间: 2023-09-14 00:34:17
class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
# 将物品按价格升序排序
items.sort(key=lambda x: x[0])
n = len(items)
# 按定义修改美丽值
for i in range(1, n):
items[i][1] = max(items[i][1], items[i-1][1])
# 二分查找处理查询
def query(q: int) -> int:
l, r = 0, n
while l < r:
mid = l + (r - l) // 2
if items[mid][0] > q:
r = mid
else:
l = mid + 1
if l == 0:
# 此时所有物品价格均大于查询价格
return 0
else:
# 返回小于等于查询价格的物品的最大美丽值
return items[l-1][1]
res = [query(q) for q in queries]
return res
python3 解法, 执行用时: 676 ms, 内存消耗: 64.7 MB, 提交时间: 2023-09-14 00:34:03
from sortedcontainers import SortedList
class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
res = {}
s = SortedList(items)
s2 = SortedList([i[::-1] for i in items])
for i in sorted(queries)[::-1]:
while s and s[-1][0] > i:
s2.remove(s.pop()[::-1])
res[i] = s2[-1][0] if s2 else 0
ans = []
for i in queries:
ans.append(res[i])
return ans
golang 解法, 执行用时: 204 ms, 内存消耗: 22.2 MB, 提交时间: 2023-09-14 00:33:37
func maximumBeauty(items [][]int, queries []int) []int {
sort.Slice(items, func(i, j int) bool { return items[i][0] < items[j][0] }) // 按价格排序
for i, q := range queries {
queries[i] = q<<32 | i // 这样排序时可以保留查询的下标
}
sort.Ints(queries)
ans := make([]int, len(queries))
maxBeauty, i := 0, 0
for _, q := range queries {
for ; i < len(items) && items[i][0] <= q>>32; i++ {
if items[i][1] > maxBeauty {
maxBeauty = items[i][1]
}
}
ans[q&(1<<32-1)] = maxBeauty
}
return ans
}