哈哈，LeetCode 2813！这道题可是 **2024 年 Meta（Facebook）周赛** 的压轴题，难度不小，但思路一旦打通就特别爽～
而且它和 2809 完全不同风格：**贪心 + 哈希 + 反悔策略**，超有代表性！
我来用朋友聊天的方式，带你一步步拆解，最后给你一个**清晰、高效、可 AC 的 Java 实现** 💪
---
### 🌟 题目大意（简化版）
你有一组物品，每个物品有：
- `profit`（利润）
- `category`（类别）
你要选出 **恰好 k 个物品**，组成一个子序列（顺序不重要），使得 **“优雅度”最大**。
> **优雅度 = 总利润 + (不同类别数)²**
目标：求最大优雅度。
---
### 💡 核心洞察
优雅度由两部分组成：
1. **总利润** → 越大越好
2. **类别多样性** → 类别越多，平方项增长越快（比如 3²=9，4²=16，跳得很快！）
所以不能只选利润最高的 k 个（可能全是同一类），也不能只追求数量（低利润拉垮总分）。
✅ **策略：先贪心选利润最高的 k 个，再尝试“替换”来增加类别数！**
---
### 🔑 关键步骤（反悔贪心）
1. **按利润降序排序** → 优先考虑高利润
2. **选前 k 个**，计算初始优雅度
- 用 `Set` 记录已有类别
- 用 `Stack`（或 List）记录**重复类别中利润最小的那些**（可以被替换掉的）
3. **从第 k+1 个开始遍历**（剩下的低利润物品）：
- 如果它的类别**没见过**，并且我们**有重复项可替换**：
- 用它替换掉重复项中利润最小的那个
- 更新总利润、类别数、优雅度
- 一旦无法再增加新类别（或没重复项了），就可以 break（因为后面利润更低，不会更优）
> ✨ 这叫 **“反悔贪心”**：先做局部最优（选高利润），再允许“后悔”来换取全局更优（加新类别）。
---
### ✅ Java 实现（带详细注释）
```java
import java.util.*;
class Solution {
public long findMaximumElegance(int[][] items, int k) {
int n = items.length;
// 1. 按利润降序排序
Arrays.sort(items, (a, b) -> Integer.compare(b[0], a[0]));
long totalProfit = 0;
Set<Integer> seenCategories = new HashSet<>();
Deque<Integer> duplicateProfits = new ArrayDeque<>(); // 存重复类别的利润（栈顶最小）
// 2. 选前 k 个
for (int i = 0; i < k; i++) {
int profit = items[i][0];
int category = items[i][1];
totalProfit += profit;
if (!seenCategories.add(category)) {
// 类别已存在 → 是重复项，加入栈（注意：栈底大，栈顶小？不，我们后面要弹最小的）
duplicateProfits.push(profit);
}
}
// 初始优雅度
long maxElegance = totalProfit + (long) seenCategories.size() * seenCategories.size();
// 3. 尝试用后面的物品替换重复项，增加新类别
for (int i = k; i < n; i++) {
int profit = items[i][0];
int category = items[i][1];
// 只有当：1) 新类别 2) 有重复项可替换
if (!seenCategories.contains(category) && !duplicateProfits.isEmpty()) {
// 替换：去掉一个重复的最小利润，加入这个新类别
int removedProfit = duplicateProfits.pop(); // 弹出的是之前 push 的，但注意：我们没保证栈内有序！
totalProfit = totalProfit - removedProfit + profit;
seenCategories.add(category);
long elegance = totalProfit + (long) seenCategories.size() * seenCategories.size();
if (elegance > maxElegance) {
maxElegance = elegance;
}
}
}
return maxElegance;
}
}
```
---
### ⚠️ 重要细节：**duplicateProfits 必须是“递减栈”吗？**
其实不用！因为我们是**按利润降序处理前 k 个**，所以：
- 第一个遇到的重复项，利润 ≥ 后面的重复项
- 所以 `duplicateProfits` 用普通栈（LIFO）即可，**栈顶就是当前重复项中利润最小的**！
举个例子：
前 k 个利润：[10, 9, 8, 7, 6]
类别：[A, B, A, C, B]
→ 重复项是第 3 个（A,8）和第 5 个（B,6）
→ `duplicateProfits` 先 push 8，再 push 6 → 栈：[6, 8]（栈顶=6）
→ 弹出时先弹 6（最小），完美！
✅ 所以 **不需要优先队列**，普通栈足够！
---
### 🧪 举个测试用例
```text
items = [[3,2],[5,1],[10,1]], k = 2
排序后: [[10,1], [5,1], [3,2]]
选前 2: [10,1], [5,1] → profit=15, categories={1} → elegance=15+1=16
剩下: [3,2] → 新类别 2，且有重复项（两个1）
替换：去掉 5（重复中较小的），加入 3 → profit=10+3=13, categories={1,2} → elegance=13+4=17 ✅
```
---
### 📊 复杂度
- **时间**：O(n log n)（排序主导）
- **空间**：O(n)
---
### 💬 最后唠两句
这道题真的超经典！面试官特别爱考这种 **“贪心 + 反悔”** 的组合，既能看算法思维，又能看代码细节。
如果你已经理解了，不妨试试自己写一遍～
要是还想看 **Go / Python 版本**，或者想挑战类似的题（比如 LeetCode 2599、2818），随时喊我！😄
P.S. 你觉得 Meta 出这题是不是在暗示他们喜欢“多样性”？🤣
