Medium

题目描述

给你一个二维整数数组 items，其中 items[i] = [pricei, beautyi] 分别表示第 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^5
  • items[i].length == 2
  • 1 <= pricei, beautyi, queries[j] <= 10^9

解题思路

这道题的核心思想是预处理和二分查找的结合使用。

思路分析：

  1. 排序预处理：首先按价格对物品进行排序，这样我们可以利用有序性进行二分查找。

  2. 美丽值最大化：对于每个价格点，我们需要知道价格不超过该值的所有物品中的最大美丽值。我们可以在排序后遍历一遍，维护一个前缀最大美丽值数组。

  3. 去重优化：如果多个物品价格相同，我们只需要保留美丽值最大的那个，这样可以减少数据规模。

  4. 二分查找：对于每个查询，使用二分查找找到价格不超过查询值的最后一个物品位置，然后返回对应的最大美丽值。

算法步骤：

  • 按价格排序items数组
  • 处理相同价格的物品，只保留美丽值最大的
  • 计算每个位置的前缀最大美丽值
  • 对每个查询进行二分查找

时间复杂度主要来自排序和查询阶段的二分查找，整体效率很高。

代码实现

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        // 按价格排序
        sort(items.begin(), items.end());
        
        // 去除相同价格的物品，只保留美丽值最大的
        vector<vector<int>> processed;
        for (auto& item : items) {
            if (processed.empty() || processed.back()[0] != item[0]) {
                processed.push_back(item);
            } else {
                processed.back()[1] = max(processed.back()[1], item[1]);
            }
        }
        
        // 计算前缀最大美丽值
        for (int i = 1; i < processed.size(); i++) {
            processed[i][1] = max(processed[i][1], processed[i-1][1]);
        }
        
        vector<int> result;
        for (int query : queries) {
            // 二分查找最后一个价格 <= query 的物品
            int left = 0, right = processed.size() - 1, ans = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (processed[mid][0] <= query) {
                    ans = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            result.push_back(ans == -1 ? 0 : processed[ans][1]);
        }
        
        return result;
    }
};

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        # 按价格排序
        items.sort()
        
        # 去除相同价格的物品，只保留美丽值最大的
        processed = []
        for price, beauty in items:
            if not processed or processed[-1][0] != price:
                processed.append([price, beauty])
            else:
                processed[-1][1] = max(processed[-1][1], beauty)
        
        # 计算前缀最大美丽值
        for i in range(1, len(processed)):
            processed[i][1] = max(processed[i][1], processed[i-1][1])
        
        result = []
        for query in queries:
            # 二分查找最后一个价格 <= query 的物品
            left, right = 0, len(processed) - 1
            ans = -1
            while left <= right:
                mid = (left + right) // 2
                if processed[mid][0] <= query:
                    ans = mid
                    left = mid + 1
                else:
                    right = mid - 1
            result.append(0 if ans == -1 else processed[ans][1])
        
        return result

public class Solution {
    public int[] MaximumBeauty(int[][] items, int[] queries) {
        // 按价格排序
        Array.Sort(items, (a, b) => a[0].CompareTo(b[0]));
        
        // 去除相同价格的物品，只保留美丽值最大的
        List<int[]> processed = new List<int[]>();
        foreach (var item in items) {
            if (processed.Count == 0 || processed[processed.Count - 1][0] != item[0]) {
                processed.Add(new int[] { item[0], item[1] });
            } else {
                processed[processed.Count - 1][1] = Math.Max(processed[processed.Count - 1][1], item[1]);
            }
        }
        
        // 计算前缀最大美丽值
        for (int i = 1; i < processed.Count; i++) {
            processed[i][1] = Math.Max(processed[i][1], processed[i - 1][1]);
        }
        
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            // 二分查找最后一个价格 <= query 的物品
            int left = 0, right = processed.Count - 1, ans = -1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (processed[mid][0] <= queries[i]) {
                    ans = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            result[i] = ans == -1 ? 0 : processed[ans][1];
        }
        
        return result;
    }
}

var maximumBeauty = function(items, queries) {
    items.sort((a, b) => a[0] - b[0]);
    
    let maxBeauty = 0;
    for (let i = 0; i < items.length; i++) {
        maxBeauty = Math.max(maxBeauty, items[i][1]);
        items[i][1] = maxBeauty;
    }
    
    const result = [];
    for (let query of queries) {
        let left = 0, right = items.length - 1;
        let answer = 0;
        
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (items[mid][0] <= query) {
                answer = items[mid][1];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        result.push(answer);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n log n + m log n)，其中 n 是 items 的长度，m 是 queries 的长度。排序需要 O(n log n)，每个查询的二分查找需要 O(log n)
空间复杂度O(n)，用于存储处理后的物品数组

相关题目