5912. 每一個查詢的最大美麗值

給你一個二維整數(shù)數(shù)組 items ，其中 items[i] = [pricei, beautyi] 分別表示每一個物品的 價(jià)格 和 美麗值 。

同時給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 queries 。對于每個查詢 queries[j] ，你想求出價(jià)格小于等于 queries[j] 的物品中，最大的美麗值 是多少。如果不存在符合條件的物品，那么查詢的結(jié)果為 0 。

請你返回一個長度與 queries 相同的數(shù)組 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] 是唯一價(jià)格 <= 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] 解釋： 每個物品的價(jià)格均為 1 ，所以我們選擇最大美麗值 4 。 注意，多個物品可能有相同的價(jià)格和美麗值。示例 3：輸入：items = [[10,1000]], queries = [5] 輸出：[0] 解釋： 沒有物品的價(jià)格小于等于 5 ，所以沒有物品可以選擇。 因此，查詢的結(jié)果為 0 。

提示：

• 1 <= items.length, queries.length <= $10^5$
• items[i].length == 2
• 1 <= pricei, beautyi, queries[j] <= $10^9$

解題思路

對items數(shù)組按照價(jià)格大小進(jìn)行排序

維護(hù)前綴最大美麗值數(shù)組，b[i]代表在當(dāng)前下標(biāo)i之前，出現(xiàn)的最大美麗值

對于每一個查詢，使用二分查找，找出 小于等于 queries[j]中具有最大價(jià)格物品，根據(jù)前綴最大美麗值數(shù)組，可以得出小于等于 queries[j]物品中的最大美麗值

代碼

class Solution { public:vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {sort(items.begin(),items.end());int m=items[0][1];int n=items.size();vector<int> b(n);vector<int> a(n);for (int i = 0; i < n; ++i) {m=max(m,items[i][1]);b[i]=m;a[i]=items[i][0];}vector<int> res(queries.size());for (int i = 0; i < queries.size(); ++i) {int idx=upper_bound(a.begin(),a.end(),queries[i])-a.begin();if (idx==0)res[i]=0;else res[i]=b[idx-1];}return res;}};

總結(jié)

以上是生活随笔為你收集整理的5912. 每一个查询的最大美丽值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。