[LeetCode] 每日一题 2070. 每一个查询的最大美丽值

题目链接

https://leetcode.cn/problems/most-beautiful-item-for-each-query

题目描述

给你一个二维整数数组 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

解题思路

本题的核心思路是 排序 + 二分查找。首先，我们按照 价格升序、美丽值降序 对 items 进行排序，确保相同价格时优先保留更高的美丽值。然后，我们 遍历数组，更新 items[i][1] 为 当前价格及之前价格的最大美丽值，这样就能保证查询时，每个价格区间的最大美丽值都是正确的

对于每个查询 queries[j]，我们使用 二分查找 找到价格 <= queries[j] 的最大索引 i，然后返回 items[i][1] 作为结果。如果 queries[j] 过小，直接返回 0；如果 queries[j] 足够大，直接返回 items 最后一个美丽值

代码实现

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        Arrays.sort(items, (e1, e2) -> {
            if (e1[0] != e2[0]) {
                return e1[0] - e2[0];
            }
            return e2[1] - e1[1];
        });
        // 预处理：使得 items[i][1] 变成当前价格及之前价格的最大美丽值
        for (int i = 1; i < items.length; i++) {
            items[i][1] = Math.max(items[i][1], items[i - 1][1]);
        }
        int[] answers = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            answers[i] = find(items, queries[i]);
        }
        return answers;
    }

    private int find(int[][] items, int query) {
        if (items[0][0] > query) {
            return 0;
        }
        if (items[items.length - 1][0] <= query) {
            return items[items.length - 1][1];
        }
        int left = 0, right = items.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (items[mid][0] <= query) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return items[left][1];
    }
}

复杂度分析

• 时间复杂度: O(n log n + m log n)，其中 n 是 items 的大小，m 是 queries 的大小。排序 O(n log n)，二分查找 O(log n)，总共有 m 个查询

• 空间复杂度: O(1)，除了输入输出外，我们只修改 items，没有使用额外的空间

总结

这道题的关键点是 排序+二分查找 的结合。刚开始我没有注意到需要更新 items[i][1] 为当前及之前的最大美丽值，导致查询结果错误。后续修正后，通过 二分查找 直接找到价格 <= queries[j] 的最大美丽值，使得查询效率达到 O(log n)，整体解法非常高效

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。