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

給你一個二維整數數組 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$

解題思路

1. 對items數組按照價格大小進行排序
2. 維護前綴最大美麗值數組，b[i]代表在當前下標i之前，出現的最大美麗值
3. 對于每一個查詢，使用二分查找，找出 小于等于 queries[j]中具有最大價格物品，根據前綴最大美麗值數組，可以得出小于等于 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;}};