从Leetcode 每日一题练习继续讨论：
2070. 每一个查询的最大美丽值
2070. Most Beautiful Item for Each Query
题解
本题要求对每个query，不大于该query的price能得到的最大beauty是多少。则一定需要在items中查找满足不大于query的price最大是多少，查找无疑使用经典的二分查找，二分查找需要数组是有序的，因此需要给items排序，排序后，考虑items中存在相同price对应不同的beauty，并且有可能更小的price却能得到更大的beauty，故遍历一遍有序items在过滤掉重复的price的同时，将每个price对应的beauty设置为不大于该price的所有price中能得到的beauty的最大值。再根据query的值对price二分查找，找到不大于query的最大price，其对应的beauty即为该query对应的beauty。
代码
class Solution {
public:
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
sort(items.begin(), items.end());
vector<vector<int>> newitems;
int lastprice = 0;
int maxbeauty = 0;
for (auto &item : items) {
if (item[0] != lastprice) {
newitems.emplace_back(item);
lastprice = item[0];
}
if (maxbeauty < item[1]) {
maxbeauty = item[1];
}
newitems.back()[1] = maxbeauty;
}
vector<int> sols;
sols.reserve(queries.size());
for (int query : queries) {
// 手动实现二分查找，找到第一个价格大于查询值的位置
int left = 0;
int right = newitems.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (newitems[mid][0] <= query) {
left = mid + 1;
} else {
right = mid;
}
}
if (left == 0) {
sols.push_back(0);
} else {
sols.push_back(newitems[left - 1][1]);
}
}
return sols;
}
};
总结
其实过滤重复的price对本题影响不大，即使有重复的price也不影响二分查找最终找到的最大的满足条件的price和其对应的最大beauty，因此可以直接修改有序items数组，仅修改每个item的beauty为不大于该price的最大beauty即可
class Solution {
public:
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
sort(items.begin(), items.end());
int maxbeauty = 0;
for (auto &item : items) {
if (maxbeauty < item[1]) {
maxbeauty = item[1];
}
item[1] = maxbeauty;
}
vector<int> sols;
for (int query : queries) {
// 手动实现二分查找，找到第一个价格大于查询值的位置
int left = 0;
int right = items.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (items[mid][0] <= query) {
left = mid + 1;
} else {
right = mid;
}
}
if (left == 0) {
sols.push_back(0);
} else {
sols.push_back(items[left - 1][1]);
}
}
return sols;
}
};