力扣每日一题（2024-06-13）2813. 子序列最大优雅度

 基于官方题解，进行补充说明

给你一个长度为 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

步骤

1. 初始化变量：

   • categorySet：用于记录当前子序列中出现的不同类别。

   • profit：记录当前子序列的总利润。

   • res：记录最大的优雅度。

   • st：用来记录那些在子序列中出现了多次的类别的项目的利润。

2. 排序：首先按利润从高到低对项目进行排序。这样可以确保我们在选择前 k 个项目时，总利润是最大的。

3. 遍历项目：对排序后的项目进行遍历。

   • 如果当前项目在前 k 个范围内（即子序列还没有达到长度 k）：

     • 将其利润加入 profit。

     • 将其类别加入 categorySet，如果类别已经存在，则将利润压入 st 堆栈中。

   • 如果当前项目在 k+1 项目之后（即子序列已经达到长度 k），并且 st 堆栈不为空，且当前项目的类别不在 categorySet 中：

     • 从 st 中弹出一个利润最小的项目，用当前项目替换它，增加 profit 和 categorySet。

4. 计算优雅度：在每次更新 profit 和 categorySet 后，计算当前优雅度，并更新最大优雅度 res。

主要逻辑解释

1. 排序：Arrays.sort(items, (item0, item1) -> item1[0] - item0[0]);

   • 这个步骤确保我们优先选择利润高的项目，以保证前 k 个项目的总利润最大。

2. 前 k 项目：

   if (i < k) {
       profit += items[i][0];
       if (!categorySet.add(items[i][1])) {
           st.push(items[i][0]);
       }

   • 对于前 k 个项目，直接将利润加入总利润 profit。

   • 将项目的类别加入 categorySet，如果类别已经存在，则将利润压入 st 堆栈中。

3. 替换逻辑：

   else if (!st.isEmpty() && categorySet.add(items[i][1])) {
       profit += items[i][0] - st.pop();
   }

   • 对于第 k+1 项目之后的项目，如果 st 堆栈不为空，且当前项目的类别不在 categorySet 中：

     • 从 st 中弹出一个利润最小的项目，并用当前项目替换它。这样确保增加新的类别，同时总利润减少最少。

4. 计算优雅度：

   res = Math.max(res, profit + (long)categorySet.size() * categorySet.size());

   • 每次更新 profit 和 categorySet 后，计算当前优雅度，并更新最大优雅度 res。

代码

class Solution {
    // 初始化变量
    Set<Integer> categorySet = new HashSet<>(); // 用于记录当前子序列中出现的不同类别
    long profit = 0; // 当前子序列的总利润
    long res = 0; // 记录最大的优雅度
    Deque<Integer> st = new ArrayDeque<>(); // 记录重复类别项目的利润

    public long findMaximumElegance(int[][] items, int k) {
        // 按利润从高到低排序
        Arrays.sort(items, (item0, item1) -> item1[0] - item0[0]);

        for (int i = 0; i < items.length; i++ ) {
            
            if (i < k) {
            // 在前 k 个项目中
                // 将项目的利润加入总利润
                profit += items[i][0];
                if (!categorySet.add(items[i][1])) {
                    // 如果类别已经存在于 categorySet 中，将利润压入堆栈。以便后面替换
                    st.push(items[i][0]);
                }
            } else if (!st.isEmpty() && categorySet.add(items[i][1])) {
            // 在第 k+1 项目及之后，并且当前项目的类别不在 categorySet 中
            // 且堆栈不为空时，进行替换操作

                // 用当前项目替换利润最小的重复类别项目
                profit += items[i][0] - st.pop();
            }
            // 计算当前优雅度并更新最大优雅度
            res = Math.max(res, profit + (long)categorySet.size() * categorySet.size());
        }
        // 返回最大优雅度
        return res;
    }
}

详解 st 队列

st 的作用是在处理项目时，用于记录那些在子序列中类别出现重复的项目的利润。具体来说，当 st 不为空且当前项目的类别与已选子序列中的所有类别都不相同时，可以通过从 st 弹出一个利润最小的项目，用当前项目替换它，从而增加不同类别的数量，并尽量减少总利润的减少。下面是更详细的解释：

st 的作用

1. 记录重复类别的项目利润：当一个项目的类别在子序列中已经存在时，将其利润值记录到 st 中。这是因为这些项目不会增加不同类别的数量，但它们的利润可能在后续处理中被替换掉。

2. 替换以增加不同类别的数量：在处理第 k+1 个及之后的项目时，如果当前项目的类别不在已选子序列的类别集合 categorySet 中，并且 st 不为空，可以将当前项目的利润与 st 中最小的利润值进行替换，从而增加不同类别的数量并尽量保持总利润的最大化。

详细解释

假设我们当前已经选择了前 k 个项目，这时 categorySet 中记录了这些项目的类别。如果其中某些类别重复了，那么这些重复类别项目的利润将被压入 st。当我们处理第 k+1 个及之后的项目时：

1. 如果当前项目的类别不在 categorySet 中，且 st 不为空：

   • 我们可以将 st 中最小的利润值弹出，并用当前项目替换它。这样做有两个好处：

     • 增加不同类别的数量。

     • 尽量减少总利润的减少，因为我们选择了 st 中最小的利润值进行替换。

代码示例中的 st 用法

for (int i = 0; i < items.length; i++) {
    if (i < k) {
        profit += items[i][0];
        if (!categorySet.add(items[i][1])) {
            st.push(items[i][0]);
        }
    } else if (!st.isEmpty() && categorySet.add(items[i][1])) {
        profit += items[i][0] - st.pop();
    }
    res = Math.max(res, profit + (long)categorySet.size() * categorySet.size());
}

分步解释

1. 处理前 k 个项目：

   • profit += items[i][0];：将利润加到总利润中。

   • if (!categorySet.add(items[i][1])) { st.push(items[i][0]); }：

     • 如果项目类别已经存在于 categorySet 中，将其利润值压入 st。

2. 处理第 k+1 个及之后的项目：

   • else if (!st.isEmpty() && categorySet.add(items[i][1])) { profit += items[i][0] - st.pop(); }：

     • 如果当前项目的类别不在 categorySet 中，且 st 不为空，弹出 st 中最小的利润值（假设 st 是一个优先队列，能够快速获得最小值），并用当前项目的利润替换它。