2813. 最大 K 长度子序列的优雅度

Hard

题目描述

给你一个长度为 n 的二维整数数组 items 和一个整数 k。

items[i] = [profiti, categoryi]，其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。

现在定义 items 的子序列的 优雅度 可以用 total_profit + distinct_categories² 计算，其中 total_profit 是子序列中所有利润的总和，distinct_categories 是所选子序列所含的不同类别数量。

你的任务是从 items 的所有长度为 k 的子序列中，找出 最大优雅度。

返回所有长度恰好为 k 的子序列中的最大优雅度。

**注意：**数组的子序列是通过删除原数组中的一些元素（可能不删除）而不改变其余元素的相对顺序所生成的新数组。

示例 1：

输入：items = [[3,2],[5,1],[10,1]], k = 2
输出：17
解释：在这个例子中，我们需要选择一个长度为 2 的子序列。
我们可以选择 items[0] = [3,2] 和 items[2] = [10,1]。
这个子序列的总利润为 3 + 10 = 13，子序列包含 2 个不同的类别 [2,1]。
因此优雅度为 13 + 2² = 17，我们可以证明这是能达到的最大优雅度。

示例 2：

输入：items = [[3,1],[3,1],[2,2],[5,3]], k = 3
输出：19
解释：在这个例子中，我们需要选择一个长度为 3 的子序列。
我们可以选择 items[0] = [3,1]，items[2] = [2,2] 和 items[3] = [5,3]。
这个子序列的总利润为 3 + 2 + 5 = 10，子序列包含 3 个不同的类别 [1,2,3]。
因此优雅度为 10 + 3² = 19，我们可以证明这是能达到的最大优雅度。

示例 3：

输入：items = [[1,1],[2,1],[3,1]], k = 3
输出：7
解释：在这个例子中，我们需要选择一个长度为 3 的子序列。
我们应该选择所有的项目。
总利润为 1 + 2 + 3 = 6，子序列包含 1 个不同的类别 [1]。
因此最大优雅度为 6 + 1² = 7。

提示：

1 <= items.length == n <= 10⁵
items[i].length == 2
items[i][0] == profiti
items[i][1] == categoryi
1 <= profiti <= 10⁹
1 <= categoryi <= n
1 <= k <= n

解题思路

这是一道贪心算法题目，核心思想是通过动态调整选择的物品来最大化优雅度。

解题思路：

排序策略：首先按利润从高到低对所有物品排序，这样能保证我们优先考虑高利润的物品。
初始选择：选择前 k 个利润最高的物品作为初始候选集合，计算初始优雅度。
动态替换：对于剩余的 n-k 个物品，尝试用它们替换候选集合中的物品来增加优雅度。替换策略如下：
- 只考虑能带来新类别的物品（即该类别在当前候选集合中不存在）
- 如果要替换，选择候选集合中利润最小且类别重复的物品进行替换
- 使用栈来维护可被替换的重复类别物品，按利润从小到大排序
优雅度更新：每次成功替换后，总利润可能下降，但不同类别数增加，需要重新计算优雅度并更新最大值。

关键点：

使用哈希表记录已选择的类别
使用栈维护可替换的重复物品（按利润升序）
只有当新物品能增加类别数且存在可替换的重复物品时才进行替换

这种贪心策略能确保在每一步都做出最优决策，最终得到全局最优解。

代码实现

class Solution {
public:
    long long findMaximumElegance(vector<vector<int>>& items, int k) {
        sort(items.begin(), items.end(), [](const auto& a, const auto& b) {
            return a[0] > b[0];
        });
        
        long long totalProfit = 0;
        unordered_set<int> categories;
        stack<int> duplicates; // 存储重复类别物品的利润
        
        // 选择前k个物品
        for (int i = 0; i < k; i++) {
            int profit = items[i][0];
            int category = items[i][1];
            
            totalProfit += profit;
            if (categories.count(category)) {
                duplicates.push(profit);
            } else {
                categories.insert(category);
            }
        }
        
        long long maxElegance = totalProfit + (long long)categories.size() * categories.size();
        
        // 尝试替换
        for (int i = k; i < items.size(); i++) {
            int profit = items[i][0];
            int category = items[i][1];
            
            // 只考虑新类别且有可替换的重复物品
            if (!categories.count(category) && !duplicates.empty()) {
                totalProfit -= duplicates.top();
                duplicates.pop();
                totalProfit += profit;
                categories.insert(category);
                
                long long elegance = totalProfit + (long long)categories.size() * categories.size();
                maxElegance = max(maxElegance, elegance);
            }
        }
        
        return maxElegance;
    }
};

class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        items.sort(key=lambda x: -x[0])
        
        total_profit = 0
        categories = set()
        duplicates = []  # 存储重复类别物品的利润
        
        # 选择前k个物品
        for i in range(k):
            profit, category = items[i]
            total_profit += profit
            if category in categories:
                duplicates.append(profit)
            else:
                categories.add(category)
        
        max_elegance = total_profit + len(categories) ** 2
        
        # 尝试替换
        for i in range(k, len(items)):
            profit, category = items[i]
            
            # 只考虑新类别且有可替换的重复物品
            if category not in categories and duplicates:
                total_profit -= duplicates.pop()
                total_profit += profit
                categories.add(category)
                
                elegance = total_profit + len(categories) ** 2
                max_elegance = max(max_elegance, elegance)
        
        return max_elegance

public class Solution {
    public long FindMaximumElegance(int[][] items, int k) {
        Array.Sort(items, (a, b) => b[0].CompareTo(a[0]));
        
        long totalProfit = 0;
        var categories = new HashSet<int>();
        var duplicates = new Stack<int>(); // 存储重复类别物品的利润
        
        // 选择前k个物品
        for (int i = 0; i < k; i++) {
            int profit = items[i][0];
            int category = items[i][1];
            
            totalProfit += profit;
            if (categories.Contains(category)) {
                duplicates.Push(profit);
            } else {
                categories.Add(category);
            }
        }
        
        long maxElegance = totalProfit + (long)categories.Count * categories.Count;
        
        // 尝试替换
        for (int i = k; i < items.Length; i++) {
            int profit = items[i][0];
            int category = items[i][1];
            
            // 只考虑新类别且有可替换的重复物品
            if (!categories.Contains(category) && duplicates.Count > 0) {
                totalProfit -= duplicates.Pop();
                totalProfit += profit;
                categories.Add(category);
                
                long elegance = totalProfit + (long)categories.Count * categories.Count;
                maxElegance = Math.Max(maxElegance, elegance);
            }
        }
        
        return maxElegance;
    }
}

var findMaximumElegance = function(items, k) {
    items.sort((a, b) => b[0] - a[0]);
    
    let totalProfit = 0;
    const categories = new Set();
    const duplicates = []; // 存储重复类别物品的利润
    
    // 选择前k个物品
    for (let i = 0; i < k; i++) {
        const [profit, category] = items[i];
        totalProfit += profit;
        if (categories.has(category)) {
            duplicates.push(profit);
        } else {
            categories.add(category);
        }
    }
    
    let maxElegance = totalProfit + categories.size * categories.size;
    
    // 尝试替换
    for (let i = k; i < items.length; i++) {
        const [profit, category] = items[i];
        
        // 只考虑新类别且有可替换的重复物品
        if (!categories.has(category) && duplicates.length > 0) {
            totalProfit -= duplicates.pop();
            totalProfit += profit;
            categories.add(category);
            
            const elegance = totalProfit + categories.size * categories.size;
            maxElegance = Math.max(maxElegance, elegance);
        }
    }
    
    return maxElegance;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度
时间复杂度	O(n log n)
空间复杂度	O(n)

说明：

时间复杂度：主要由排序操作决定，为 O(n log n)，后续的遍历和栈操作均为 O(n)
空间复杂度：需要存储类别集合、重复物品栈等，最坏情况下为 O(n)

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目