What is the key strategy for Most Beautiful Item for Each Query?

Sort items by price, maintain a running maximum beauty, and process queries in sorted order to efficiently answer using a binary search approach.

Can multiple items with the same price affect the answer?

Yes, always consider the item with the maximum beauty among duplicates to ensure correct query results.

How do I handle queries that have no affordable items?

Return 0 for any query whose budget is less than the lowest priced item.

What is the time complexity for this pattern?

Sorting items and queries is O(M log M + N log N) and answering queries incrementally is O(M + N), yielding overall efficient performance.

Why is this considered binary search over the answer space?

Instead of searching indices directly, we check which items satisfy the budget constraints, effectively performing a search over valid item prices for each query.

#2070

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

每一个查询的最大美丽值

给你一个二维整数数组 items ，其中 items[i] = [price i , beauty i ] 分别表示每一个物品的价格和美丽值。同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中…

数组二分查找排序

题目描述

给你一个二维整数数组 items ，其中 items[i] = [price_i, beauty_i] 分别表示每一个物品的价格和 美丽值 。

同时给你一个下标从 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⁵
items[i].length == 2
1 <= price_i, beauty_i, queries[j] <= 10⁹

lightbulb

解题思路

方法一：排序 + 离线查询

对于每一个查询，我们需要找到价格小于等于查询价格的物品中的最大美丽值，我们不妨采用离线查询的方式，先对物品按价格排序，然后对查询按照价格排序。

接下来，我们从小到大遍历查询，对于每一个查询，我们用一个指针 $i$ 指向物品数组，如果物品的价格小于等于查询价格，我们更新当前的最大美丽值，向右移动指针 $i$ ，直到物品的价格大于查询价格，我们将当前的最大美丽值记录下来，就是当前查询的答案。继续遍历下一个查询，直到所有的查询都处理完。

时间复杂度 $(n \times \log n + m \times \log m)$ ，空间复杂度 $O(\log n + m)$ 。其中 $n$ 和 $m$ 分别为物品数组和查询数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items.sort()
        n, m = len(items), len(queries)
        ans = [0] * len(queries)
        i = mx = 0
        for q, j in sorted(zip(queries, range(m))):
            while i < n and items[i][0] <= q:
                mx = max(mx, items[i][1])
                i += 1
            ans[j] = mx
        return ans

speed

复杂度分析

指标	值
时间	O(M \cdot \log M + N \cdot \log N)
空间	O(S_M + S_N + N)

psychology

面试官常问的追问

外企场景

question_mark
Ask about optimizing query processing to avoid scanning all items for each query.
question_mark
Probe understanding of binary search applied over an answer space rather than indices.
question_mark
Check if candidate recognizes the need to maintain running maximum beauty while iterating.

warning

常见陷阱

外企场景

error
Ignoring multiple items with the same price and not picking the maximum beauty among them.
error
Processing queries in arbitrary order, causing repeated item scans and higher complexity.
error
Forgetting to handle queries with no affordable items, resulting in incorrect zeros.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Items may have duplicate prices but different beauties; consider keeping only the maximum beauty per price.
arrow_right_alt
Queries could be very large numbers; ensure binary search or pointer logic efficiently handles these ranges.
arrow_right_alt
Instead of a single maximum beauty, return the top K beauties for each query, requiring modified data structures.

help

常见问题

外企场景

继续练习

#2071 你可以安排的最多任务数目 #2054 两个最好的不重叠活动 #2089 找出数组排序后的目标下标