每个查询最漂亮的项目

2070。每个查询最美丽的物品

难度：中等

主题：数组、二分查找、排序

给定一个 2D 整数数组 items，其中 items[i] = [price_i, beauty_i] 表示 price 和 beauty 分别表示一个项目。

您还会获得一个 0 索引 整数数组查询。对于每个查询[j]，您想要确定其价格小于或等于查询[j]的项目的最大美度。如果不存在这样的项目，则此查询的答案为 0。

返回与查询长度相同的数组答案，其中answer[j]是第j个查询的答案。

示例1：

• 输入： 项目 = [[1,2],[3,2],[2,4],[5,6],[3,5]]，查询 = [1,2,3 ,4,5,6]
• 输出： [2,4,5,5,6,6]
• 说明：
  • 对于查询[0]=1，[1,2]是唯一价格
  • 对于查询[1]=2，可以考虑的项是[1,2]和[2,4]。
  • 其中美度最高为4。
  • 对于查询[2]=3和查询[3]=4，可以考虑的项是[1,2]、[3,2]、[2,4]和[3,5]。
  • 其中美度最高为5。
  • 对于查询[4]=5和查询[5]=6，可以考虑所有项目。
  • 因此，他们的答案是所有物品中最大的美丽，即 6。

示例2：

• 输入： 项目 = [[1,2],[1,2],[1,3],[1,4]], 查询 = [1]
• 输出： [4]
• 解释：每件商品的价格都等于1，所以我们选择颜值最高的商品4。
  • 请注意，多个商品可以具有相同的价格和/或外观。

示例 3：

• 输入： 项目 = [[10,1000]]，查询 = [5]
• 输出： [0]
• 说明：没有商品的价格小于或等于 5，因此无法选择任何商品。
  • 因此，查询的答案是 0。

约束：

• 1 5
• items[i].length == 2
• 1 i、美女_i、查询[j] 9

提示：

1. 我们能否以智能顺序处理查询以避免重复检查相同的项目？
2. 我们如何将某个查询的答案用于其他查询？

解决方案：

我们可以使用排序和二分搜索技术。计划如下：

方法

1. 按价格对商品排序：

   • 首先，按价格对商品进行排序。这样，当我们迭代这些物品时，我们可以跟踪迄今为止所看到的任何给定价格的物品的最大美丽。

2. 使用原始索引对查询进行排序:

   • 创建一个与其原始索引配对的查询数组，然后按查询值对该数组进行排序。
   • 排序很有帮助，因为我们可以按价格升序处理查询，并避免重复重新计算较低价格的美丽值。

3. 同时迭代项目和查询:

   • 使用两个指针，处理每个查询：
     • 对于每个查询，将指针移动到价格小于或等于查询价格的项目。
     • 在浏览这些项目时跟踪最大的美丽，并使用该值来回答当前的查询。
     • 这可以避免重复检查多个查询的项目。

4. 存储并返回结果:

   • 处理完成后，根据原始索引存储每个查询的最大美容结果以保持顺序。
   • 返回答案数组。

让我们用 PHP 实现这个解决方案：2070。每个查询最美丽的物品

<?php
/**
 * @param Integer[][] $items
 * @param Integer[] $queries
 * @return Integer[]
 */
function maximumBeauty($items, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$items = [[1,2],[3,2],[2,4],[5,6],[3,5]];
$queries = [1,2,3,4,5,6];
print_r(maximumBeauty($items, $queries));
// Output: [2,4,5,5,6,6]
?>

解释：

• 对项目和查询进行排序：这可以实现高效处理，无需冗余计算。
• 双指针技术：每个查询仅移动一次项目，避免过多的计算。
• 跟踪 maxBeauty：我们逐步更新 maxBeauty，允许每个查询访问迄今为止看到的最高美丽。

复杂

• 时间复杂度：O(n log nm log m) 用于对项目和查询进行排序，以及 O(n m) 用于处理，其中 n 是项目的长度，m 是查询的长度。
• 空间复杂度：O(m)用于存储结果。

这个解决方案是高效的并且满足问题的约束。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是每个查询最漂亮的项目的详细内容。更多信息请关注PHP中文网其他相关文章！