[每日一题] 2813.子序列最大优雅度

2024 年 06 月 13 日

115 次浏览

1583字数

> https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/description/?envType=daily-question&envId=2024-05-02

首先我们将 `items` 按照利润排序，并将前 $k$ 个元素选上。

接下来考虑第 $i \ (i > k)$ 个元素是否需要选。这里有以下几种情况：

- 如果第 $i$ 个元素的类型是之前出现过的，那么选上该元素后优雅度一定是减少的，因为总利润减少了且类别数没有变多。

- 如果第 $i$ 个元素的类型没有出现过，可以再分两种情况：

- 替换掉一个仅出现一次的类别，那么类别数不变，总利润减少，所以优雅度一定会减少。
  - 替换掉一个重复出现的类别，此时虽然总利润减少了，但类别数增加了，因此优雅度有可能增加。

所以遇到一个没出现过的类别，就用它替换已选中元素中重复出现且利润最少的一个元素，然后对比优雅度是否减少。注意这边一定要选上，因为后面的元素利润只会更少。

```c++
class Solution {
public:
    long long findMaximumElegance(std::vector<std::vector<int>> &items, int k) {
        const int n = items.size();
        std::sort(items.begin(), items.end(), [&](std::vector<int> &a, std::vector<int> &b) { return a[0] > b[0]; });

long long profits = 0;
        std::unordered_set<int> types;
        std::stack<int> duplicate;

for (int i = 0; i < k; i++) {
            profits += items[i][0];
            if (!types.insert(items[i][1]).second)
                duplicate.push(items[i][0]);
        }

long long res = profits + (long long)(types.size() * types.size());
        for (int i = k; i < n; i++) {
            if (duplicate.empty())
                break;

if (!types.insert(items[i][1]).second)
                continue;

profits = profits - duplicate.top() + items[i][0];
            duplicate.pop();
            res = std::max(res, profits + (long long)(types.size() * types.size()));
        }
        
        return res;
    }
};
```

- 时间复杂度：$O(nlogn)$ ，其中 $n$ 为数组 `items` 的长度。
- 空间复杂度：$O(n)$ 。

最后修改：2024 年 06 月 13 日