高淳哪家做网站不错,厦门建行网站首页,服务好的岑溪网站开发,重庆长寿网站设计公司LeetCode
子序列最大优雅度
题目链接#xff1a;2813. 子序列最大优雅度 - 力扣#xff08;LeetCode#xff09;
题目描述
给你一个长度为 n 的二维整数数组 items 和一个整数 k 。
items[i] [profiti, categoryi]#xff0c;其中 profiti 和 categoryi 分别表示第 i…LeetCode
子序列最大优雅度
题目链接2813. 子序列最大优雅度 - 力扣LeetCode
题目描述
给你一个长度为 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 n 1 k n
思路
代码
C
class Solution {
public:long long findMaximumElegance(vectorvectorint items, int k) {// 把利润从大到小排序ranges::sort(items, [](const auto a, const auto b) { return a[0] b[0]; });long long ans 0, total_profit 0;unordered_setint vis;stackint duplicate; // 重复类别的利润for (int i 0; i items.size(); i) {int profit items[i][0], category items[i][1];if (i k) {total_profit profit; // 累加前 k 个项目的利润if (!vis.insert(category).second) { // 重复类别duplicate.push(profit);}} else if (!duplicate.empty() vis.insert(category).second) { // 之前没有的类别total_profit profit - duplicate.top(); // 选一个重复类别中的最小利润替换duplicate.pop();} // else比前面的利润小而且类别还重复了选它只会让 total_profit 变小vis.size() 不变优雅度不会变大ans max(ans, total_profit (long long) vis.size() * (long long) vis.size());}return ans;}
};Java
class Solution {public long findMaximumElegance(int[][] items, int k) {// 把利润从大到小排序Arrays.sort(items, (a, b) - b[0] - a[0]);long ans 0;long totalProfit 0;SetInteger vis new HashSet();DequeInteger duplicate new ArrayDeque(); // 重复类别的利润for (int i 0; i items.length; i) {int profit items[i][0];int category items[i][1];if (i k) {totalProfit profit; // 累加前 k 个项目的利润if (!vis.add(category)) { // 重复类别duplicate.push(profit);}} else if (!duplicate.isEmpty() vis.add(category)) { // 之前没有的类别totalProfit profit - duplicate.pop(); // 选一个重复类别中的最小利润替换} // else比前面的利润小而且类别还重复了选它只会让 totalProfit 变小vis.size() 不变优雅度不会变大ans Math.max(ans, totalProfit (long) vis.size() * vis.size()); // 注意 1e5*1e5 会溢出}return ans;}
}
