子序列最大优雅度

标签: 贪心 数组 哈希表 排序 堆（优先队列）

难度: Hard

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

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

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

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

用整数形式表示并返回 items 中所有长度恰好为 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 + 22 = 17 ，可以证明 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 + 32 = 19 ，可以证明 19 是可以获得的最大优雅度。

示例 3：

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

提示：

  • 1 <= items.length == n <= 105
  • items[i].length == 2
  • items[i][0] == profiti
  • items[i][1] == categoryi
  • 1 <= profiti <= 109
  • 1 <= categoryi <= n
  • 1 <= k <= n

Submission

运行时间: 141 ms

内存: 40.8 MB

class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        items.sort(key=lambda x: -x[0])
        tot = 0
        vis = set()
        dup = []
        for p, c in items[:k]:
            tot += p
            if c not in vis:
                vis.add(c)
            else:
                dup.append(p)
        ans = tot + len(vis) ** 2
        for p, c in items[k:]:
            if c in vis or not dup:
                continue
            vis.add(c)
            tot += p - dup.pop()
            ans = max(ans, tot + len(vis) ** 2)
        return ans

Explain

首先按项目利润降序对items数组进行排序，确保优先选择利润最高的项目。接着，选取前k个项目作为初始子序列，计算这些项目的总利润并记录已选择的类别。如果在这前k个项目中有重复类别的项目，将其利润存入dup列表。然后，计算初始子序列的优雅度。接下来，遍历剩余的项目，如果遇到新的类别（不在已选择的类别集合中），且dup列表非空（意味着有可以替换的低利润项目），则用当前项目替换dup中的一个项目，更新总利润，并重新计算优雅度。这样，可以尝试通过添加新类别来提高优雅度，同时尽量保持高利润。最后返回遍历过程中计算的最大优雅度。

时间复杂度: O(n log n)

空间复杂度: O(k)

# 在items排序后选择前k个项目，计算初始优雅度

class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        # 将items按利润降序排序
        items.sort(key=lambda x: -x[0])
        tot = 0  # 初始总利润
        vis = set()  # 已选择的类别集合
        dup = []  # 存储有重复类别的项目的利润
        for p, c in items[:k]:
            tot += p
            if c not in vis:
                vis.add(c)
            else:
                dup.append(p)
        ans = tot + len(vis) ** 2  # 计算初始优雅度
        # 遍历剩余项目，尝试替换以提高优雅度
        for p, c in items[k:]:
            if c in vis or not dup:
                continue  # 如果类别已存在或没有可替换的项目，则跳过
            vis.add(c)
            tot += p - dup.pop()  # 替换项目，更新总利润
            ans = max(ans, tot + len(vis) ** 2)  # 更新最大优雅度
        return ans

Explore

在初步选择项目时，优先考虑利润最高的项目是为了尽可能地提高子序列的初始总利润。虽然类别的独特性也对优雅度有贡献，但在初始阶段，高利润项目对优雅度的直接影响较大，因为优雅度的计算公式中利润直接被加和。此外，稍后在选择过程中仍有机会通过替换重复类别的低利润项目来调整，从而增加类别的独特性和整体优雅度。

在算法中，当遇到一个类别已存在于已选择的集合中时，该项目的利润会被添加到dup列表。由于项目是按利润降序排序的，因此当一个类别第二次出现时，其利润必然不高于该类别首次出现的项目。因此，放入dup列表的自然是较低的利润项目。这样做是因为，如果后续需要替换以提高类别的独特性，优先替换利润较低的项目可以最大程度保持总利润。

使用平方的方式确实会使类别数量的影响在优雅度的计算中变得更加显著。这种设计是有意为之，目的是强调类别的多样性对于优雅度的重要性。这样的设计促使算法在保持较高利润的同时，也尽可能地增加类别的独特性，从而达到一个利润与类别多样性的平衡。

遇到新类别但利润非常低的项目时，是否替换需要权衡利润与类别数量的增加。如果新类别的加入通过类别数量的增加可以显著提高优雅度（即使牺牲一些利润），那么还是值得替换的。但如果利润损失过大，导致优雅度反而下降，则不应替换。这种决策需要在实现中通过计算替换前后的优雅度来确定，选择能使优雅度最大化的操作。