LeetCode 2070. 每一个查询的最大美丽值(离线查询+排序+优先队列)

简介: LeetCode 2070. 每一个查询的最大美丽值(离线查询+排序+优先队列)

文章目录


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


2. 解题


  • 对查询进行排序,价格小的先查询,满足价格要求的,将其美丽值放入优先队列
  • 对物品排序,价格小的先遍历
class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        int n = queries.size();
        vector<int> 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];//按查询价格从小到大排序
        });
        vector<int> maxBeauty(n, 0);
        priority_queue<int> 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++

相关文章
|
4天前
力扣随机一题 哈希表 排序 数组
力扣随机一题 哈希表 排序 数组
6 1
|
19天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
22天前
|
存储 算法 数据可视化
【模拟面试问答】深入解析力扣164题:最大间距(桶排序与排序方法详解)
【模拟面试问答】深入解析力扣164题:最大间距(桶排序与排序方法详解)
|
22天前
|
存储 算法 数据可视化
深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)
深入解读力扣154题:寻找旋转排序数组中的最小值 II(多种方法及详细ASCII图解)
|
22天前
|
存储 算法 数据可视化
|
4天前
|
存储
力扣每日一题 6/19 排序+动态规划
力扣每日一题 6/19 排序+动态规划
4 0
|
18天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
19天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
22天前
|
存储 算法 搜索推荐
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
|
22天前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】