2813.子序列最大优雅度

链接：2813.子序列最大优雅度
难度：Hard
标签：栈、贪心、数组、哈希表、排序、堆（优先队列）
简介：你的任务是从 items 所有长度为 k 的子序列中，找出 最大优雅度 。

题解 1 - python

• 编辑时间：2024-06-13
• 执行用时：237ms
• 内存消耗：42.13MB
• 编程语言：python
• 解法介绍：从大到小收益排序后，遍历时记录当前类目存在的次数。

class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        items.sort(key = lambda item: -item[0])
        print(items)
        set1 = set()
        stack2 = []
        cur = 0
        for i in range(k):
            item = items[i]
            cur += item[0]
            if item[1] in set1:
                stack2.append(item[0])
            else:
                set1.add(item[1])
        res = cur + len(set1) ** 2
        for i in range(k, len(items)):
            item = items[i]
            if item[1] not in set1 and len(stack2):
                cur += item[0] - stack2.pop()
                set1.add(item[1])
            res = max(res, cur + len(set1) ** 2)
        return res