反悔贪心，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 = 0
        st = set()
        cur = []
        for i, (p, c) in enumerate(items):
            if i < k:
                s += p
                if 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:
                break
        return 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;
};