题目
给你一个长度为 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 <= 10^5$
items[i].length == 2items[i][0] ==$profit_i$items[i][1] ==$category_i$- $1 <= profit_i <= 10^9$
- $1 <= $category_i$ <= n $
- $1 <= k <= n$
分析
局部求和，肯定从大的数字开始。我们需要对profile进行排序。
类别平方，我们需要交换选中元素，不断的提升类别数量，进一步超过profile。
利用排序、集合、栈
算法描述：
- 排序，按照profile从大到小排序
- 初始化最终结果ans
- 初始化总的利润 totalProfile
- 初始化一个集合，存储类别c
- 初始化一个栈，存储重复类别c的对应的利润p
- 遍历
for i in 0-n- 如果i小于k
- 累加利润
- 如果类别出现过
- 当前利润值入栈
- else 如果栈非空，且 是新的类别
- 更新总利润
- 迭代更新ans，取老的和新的中较大的那个
- 如果i小于k
- 返回ans
class Solution {
public long findMaximumElegance(int[][] items, int k) {
Arrays.sort(items, (a, b) -> b[0] - a[0]);
long ans = 0;// 结果
long totalProfit = 0;
Set<Integer> vis = new HashSet<>();// 存储类别
Stack<Integer> proStack = new Stack<>();// 存储最后重复的类别对应的利润
for (int i = 0; i < items.length; i++) {
int p = items[i][0];
int c = items[i][1];
if (i < k) {// 先存前k个
totalProfit += p;
if (!vis.add(c)) {
proStack.push(p);// 记录类别重复的利润，后进先出，因为最后进入的最小
}
} else if (!proStack.isEmpty() && vis.add(c)) {
// 新的类别，切移除一个旧的多个类别的数字
totalProfit += p - proStack.pop();// 减去最小的利润，增加一个类别
}
}
ans = Math.max(ans, totalProfit + (long) vis.size() * vis.size());
}
return ans;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
