反悔贪心，LeetCode 2813. 子序列最大优雅度

本文主要是介绍反悔贪心，LeetCode 2813. 子序列最大优雅度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

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

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

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

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

用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。

注意：数组的子序列是经由原数组删除一些元素（可能不删除）而产生的新数组，且删除不改变其余元素相对顺序。

2、接口描述

python3

 ​

class Solution:def findMaximumElegance(self, items: List[List[int]], k: int) -> int:

cpp

 ​

class Solution {
public:long long findMaximumElegance(vector<vector<int>>& items, int k) {}
};

js

 ​

/*** @param {number[][]} items* @param {number} k* @return {number}*/
var findMaximumElegance = function(items, k) {};

3、原题链接

2813. 子序列最大优雅度

---

二、解题报告

1、思路分析

比较经典的堆式反悔贪心

如何考虑？

我们的收益来自于序列中的profit和以及不同的种类数

这样如何决策？

我们初始先将物品按照profit降序排序

然后取前k个，后面进行反悔贪心

后面物品的profit不会比前面大，如果想要让整体变大，除非种类变多

所以，我们记录前k个元素构成序列中的重复元素，然后如果后面的元素种类是新的，我们就拿掉最小的一个重复元素和其替换

过程中维护最大值即可

2、复杂度

时间复杂度： O(NlogN)空间复杂度：O(N)

3、代码详解

python3

 ​

class Solution:def findMaximumElegance(self, items: List[List[int]], k: int) -> int:items.sort(key=lambda x: -x[0])res = s = 0st = set()cur = []for i, (p, c) in enumerate(items):if i < k:s += pif c in st:cur.append(p)else:st.add(c)elif c not in st and cur:s += p - cur.pop()st.add(c)res = max(res, s + len(st) * len(st))if len(st) == k:breakreturn res

cpp

 ​

using i64 = long long;
class Solution {
public:long long findMaximumElegance(vector<vector<int>>& items, int k) {i64 res = 0, s = 0;std::sort(items.begin(), items.end(), [](auto& x, auto& y) {return x[0] > y[0];});std::vector<int> cur;std::unordered_set<int> st;for (int i = 0; i < items.size(); i ++ ) {if (i < k) {s += items[i][0];if (!st.insert(items[i][1]).second)cur.push_back(items[i][0]);}else {if (st.insert(items[i][1]).second && cur.size())s += items[i][0] - cur.back();}res = std::max(res, s + (i64)st.size() * (i64)st.size());}return res;}
};

js

 ​

/*** @param {number[][]} items* @param {number} k* @return {number}*/
var findMaximumElegance = function(items, k) {items.sort((x, y) => y[0] - x[0]);let res = 0, s = 0;let cur = [];let st = new Set();for (let i = 0; i < items.length && st.size < k; i ++ ) {if (i < k) {s += items[i][0];if (st.has(items[i][1])) cur.push(items[i][0]);else st.add(items[i][1]);}else if (cur.length && !st.has(items[i][1])) {s += items[i][0] - cur.pop();st.add(items[i][1]);}res = Math.max(res, s + st.size * st.size);}return res;
};

这篇关于反悔贪心，LeetCode 2813. 子序列最大优雅度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---