LeetCode 题解工作台
子序列最大优雅度
给你一个长度为 n 的二维整数数组 items 和一个整数 k 。 items[i] = [profit i , category i ] ，其中 profit i 和 category i 分别表示第 i 个项目的利润和类别。 现定义 items 的 子序列 的 优雅度 可以用 total_pro…
6
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们可以将所有项目按照利润从大到小排序，先选取前 个项目，计算其总利润 ，用一个哈希表 记录这 个项目的类别，用一个栈 按顺序记录这 个项目中重复类别的利润，用一个变量 记录当前的最大优雅度。 接下来，我们考虑从第 个项目开始，如果其类别已经在 中，这意味着如果选择该类别，不会使得不同的类别数量增加，因此我们可以直接跳过该项目。如果此前不存在重复类别，我们也可以直接跳过该项目。否则…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个长度为 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 <= 105items[i].length == 2items[i][0] == profitiitems[i][1] == categoryi1 <= profiti <= 1091 <= categoryi <= n1 <= k <= n
解题思路
方法一：贪心
我们可以将所有项目按照利润从大到小排序，先选取前 个项目，计算其总利润 ，用一个哈希表 记录这 个项目的类别，用一个栈 按顺序记录这 个项目中重复类别的利润，用一个变量 记录当前的最大优雅度。
接下来，我们考虑从第 个项目开始，如果其类别已经在 中，这意味着如果选择该类别，不会使得不同的类别数量增加，因此我们可以直接跳过该项目。如果此前不存在重复类别，我们也可以直接跳过该项目。否则，我们可以考虑将 栈顶的项目（即重复类别中利润最小的项目）替换为当前项目，这样可以使得总利润增加 ，同时不同类别数量增加 ，因此我们可以更新 和 。
最后，我们返回 即可。
时间复杂度 ，空间复杂度 。其中 为项目数量。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to recognize that the problem combines both profit maximization and distinct category counting.
- question_mark
Understanding the trade-off between choosing high-profit items and ensuring category diversity.
- question_mark
Proficiency in greedy algorithms and data structure usage, such as priority queues or hash tables.
常见陷阱
外企场景- error
Failing to properly balance profit maximization with distinct category counting.
- error
Not leveraging efficient data structures like heaps and hash tables, leading to unnecessary recomputation.
- error
Selecting items without considering the impact of the category count, leading to suboptimal elegance.
进阶变体
外企场景- arrow_right_alt
Minimize elegance instead of maximizing it.
- arrow_right_alt
Increase the size of the subsequence beyond k to test scalability.
- arrow_right_alt
Change the problem constraints to allow duplicate categories in the subsequence.