2813-子序列最大优雅度

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你一个长度为 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 <= 105
  • items[i].length == 2
  • items[i][0] == profiti
  • items[i][1] == categoryi
  • 1 <= profiti <= 109
  • 1 <= categoryi <= n
  • 1 <= k <= n

请看 视频讲解 第四题。

按照利润从大到小排序。先把前 k 个项目选上。

考虑选第 k+1 个项目，为了选它，我们必须从前 k 个项目中移除一个项目。

由于已经按照利润从大到小排序，选这个项目不会让 total_profit 变大，所以我们重点考虑能否让 distinct_categories 变大。

分类讨论：

  • 如果第 k+1 个项目和前面某个已选项目的类别相同，那么无论怎么移除都不会让 distinct_categories 变大，所以无需选择这个项目。
  • 如果第 k+1 个项目和前面任何已选项目的类别都不一样，考虑移除前面已选项目中的哪一个：
    • 如果移除的项目的类别只出现一次，那么选第 k+1 个项目后，distinct_categories 一减一增，保持不变，所以不考虑这种情况。
    • 如果移除的项目的类别重复出现多次，那么选第 k+1 个项目后，distinct_categories 会增加一，此时有可能会让优雅度变大，一定要选择这个项目。为什么说「一定」呢？因为 total_profit 只会变小，我们现在的目标就是让 total_profit 保持尽量大，同时让 distinct_categories 增加，那么能让 distinct_categories 增加就立刻选上！因为后面的利润更小，现在不选的话将来 total_profit 只会更小。

按照这个过程，继续考虑选择后面的项目。计算优雅度，取最大值，即为答案。

代码实现时，我们应当移除已选项目中类别和前面重复且利润最小的项目，这可以用一个栈 duplicate 来维护，由于利润从大到小排序，所以栈顶就是最小的利润。注意对于后面的项目，由于我们只考虑之前没出现过的类别，也就是说这个后面的项目的类别只出现了一次，所以不应当加到 duplicate 中。

注：这个算法叫做反悔贪心。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        items.sort(key=lambda i: -i[0])  # 把利润从大到小排序
        ans = total_profit = 0
        vis = set()
        duplicate = []  # 重复类别的利润
        for i, (profit, category) in enumerate(items):
            if i < k:
                total_profit += profit
                if category not in vis:
                    vis.add(category)
                else:  # 重复类别
                    duplicate.append(profit)
            elif duplicate and category not in vis:
                vis.add(category)
                total_profit += profit - duplicate.pop()  # 用最小利润替换
            # else: 比前面的利润小，而且类别还重复了，选它只会让 total_profit 变小，len(vis) 不变，优雅度不会变大
            ans = max(ans, total_profit + len(vis) * len(vis))
        return ans
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public long findMaximumElegance(int[][] items, int k) {
        // 把利润从大到小排序
        Arrays.sort(items, (a, b) -> b[0] - a[0]);
        long ans = 0, totalProfit = 0;
        var vis = new HashSet<Integer>();
        var duplicate = new ArrayDeque<Integer>(); // 重复类别的利润
        for (int i = 0; i < items.length; i++) {
            int profit = items[i][0], category = items[i][1];
            if (i < k) {
                totalProfit += profit;
                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;
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    long long findMaximumElegance(vector<vector<int>> &items, int k) {
        // 把利润从大到小排序
        sort(items.begin(), items.end(), [](const auto &a, const auto &b) {
            return a[0] > b[0];
        });
        long long ans = 0, total_profit = 0;
        unordered_set<int> vis;
        stack<int> duplicate; // 重复类别的利润
        for (int i = 0; i < items.size(); i++) {
            int profit = items[i][0], category = items[i][1];
            if (i < k) {
                total_profit += profit;
                if (!vis.insert(category).second) // 重复类别
                    duplicate.push(profit);
            } else if (!duplicate.empty() && vis.insert(category).second) {
                total_profit += profit - duplicate.top(); // 选一个重复类别中的最小利润替换
                duplicate.pop();
            } // else：比前面的利润小，而且类别还重复了，选它只会让 totalProfit 变小，vis.size() 不变，优雅度不会变大
            ans = max(ans, total_profit + (long long) vis.size() * (long long) vis.size());
        }
        return ans;
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func findMaximumElegance(items [][]int, k int) int64 {
	// 把利润从大到小排序
	sort.Slice(items, func(i, j int) bool { return items[i][0] > items[j][0] })
	ans, totalProfit := 0, 0
	vis := map[int]bool{}
	duplicate := []int{} // 重复类别的利润
	for i, p := range items {
		profit, category := p[0], p[1]
		if i < k {
			totalProfit += profit
			if !vis[category] {
				vis[category] = true
			} else { // 重复类别
				duplicate = append(duplicate, profit)
			}
		} else if len(duplicate) > 0 && !vis[category] {
			vis[category] = true
			totalProfit += profit - duplicate[len(duplicate)-1] // 选一个重复类别中的最小利润替换
			duplicate = duplicate[:len(duplicate)-1]
		} // else 比前面的利润小，而且类别还重复了，选它只会让 totalProfit 变小，len(vis) 不变，优雅度不会变大
		ans = max(ans, totalProfit+len(vis)*len(vis))
	}
	return int64(ans)
}

func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(n\log n)，其中 n 为 items 的长度。瓶颈在排序上。
  • 空间复杂度：\mathcal{O}(n)。
 Comments
On this page
2813-子序列最大优雅度