网站开发培训周末班,手机商城网站开发,温州开发网站公司哪家好,wordpress插件使用教程文章目录1. 题目2. 解题1. 题目
给你一个二维整数数组 items #xff0c;其中 items[i] [pricei, beautyi] 分别表示每一个物品的 价格 和 美丽值 。
同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] #xff0c;你想求出价格小于等于 queries[j]…
文章目录1. 题目2. 解题1. 题目
给你一个二维整数数组 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/most-beautiful-item-for-each-query 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
对查询进行排序价格小的先查询满足价格要求的将其美丽值放入优先队列对物品排序价格小的先遍历
class Solution {
public:vectorint maximumBeauty(vectorvectorint items, vectorint queries) {int n queries.size();vectorint idx(n);sort(items.begin(), items.end());//按价格从小到大排序iota(idx.begin(), idx.end(), 0); // 填充从 0开始的自然数sort(idx.begin(), idx.end(), [](int a, int b){return queries[a] queries[b];//按查询价格从小到大排序});vectorint maxBeauty(n, 0);priority_queueint q; // 存储美丽值int j 0;for(int i 0 ; i n; i){while(j items.size() items[j][0] queries[idx[i]]){ // 价格满足要求的将其美丽值加入优先队列q.push(items[j][1]);j;}if(!q.empty())maxBeauty[idx[i]] q.top();}return maxBeauty;}
};336 ms 88.2 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
