本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創建新題，本系列的終止日期可能是永遠。在這一系列刷題文章中，我不僅會講解多種解題思路及其優化，還會用多種編程語言實現題解，涉及到通用解法時更將歸納總結出相應的算法模板。
為了方便在PC上運行調試、分享代碼文件，我還建立了相關的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結等，還可以看到原題出現頻率和相關企業等重要信息。如果有其他優選題解，還可以一同分享給他人。
由于本系列文章的內容隨時可能發生更新變動，歡迎關注和收藏征服LeetCode系列文章目錄一文以作備忘。
給你一個長度為?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 <= 10^5items[i].length == 2items[i][0] == profitiitems[i][1] == categoryi1 <= profiti <= 10^91 <= categoryi <= n1 <= k <= n
解法 反悔貪心
按照利潤從大到小排序。先把前 k k k 個項目選上。
考慮選第 k + 1 k+1 k+1 個項目，為了選它，我們必須從前 k k k 個項目中移除一個項目。由于已經按照利潤從大到小排序，選這個項目不會讓 t o t a l _ p r o f i t total\_profit total_profit 變大，所以我們重點考慮能否讓 d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 變大。分類討論：
- 如果第 k + 1 k+1 k+1 個項目和前面某個已選項目的類別相同，那么無論怎么移除都不會讓 d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 變大，所以無需選擇這個項目。
- 如果第 k + 1 k+1 k+1 個項目和前面任何已選項目的類別都不一樣，考慮移除前面已選項目中的哪一個：
- 如果移除的項目的類別只出現一次，那么選第 k + 1 k+1 k+1 個項目后， d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 一減一增，保持不變，所以不考慮這種情況。
- 如果移除的項目的類別重復出現多次，那么選第 k + 1 k+1 k+1 個項目后， d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 會增加一，此時有可能會讓優雅度變大，一定要選擇這個項目。為什么說「一定」呢？因為 t o t a l _ p r o f i t total\_profit total_profit 只會變小，我們現在的目標就是讓 t o t a l _ p r o f i t total\_profit total_profit 保持盡量大，同時讓 d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 增加，那么能讓 d i s t i n c t _ c a t e g o r i e s distinct\_categories distinct_categories 增加就立刻選上！因為后面的利潤更小，現在不選的話將來 t o t a l _ p r o f i t total\_profit total_profit 只會更小。
按照這個過程，繼續考慮選擇后面的項目。計算優雅度，取最大值，即為答案。
代碼實現時，應移除已選項目中類別和前面重復且利潤最小的項目，這可以用一個棧 d u p l i c a t e duplicate duplicate 來維護，由于利潤從大到小排序，所以棧頂就是最小的利潤；前面 k k k 次中如果出現了多個重復項，則在棧中也會有多個項。注意，對于后面的項目，由于我們只考慮之前沒出現過的類別，也就是說這個后面的項目的類別只出現了一次，所以不應當加到 d u p l i c a t e duplicate duplicate 中。
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 totalProfit = 0, ans = 0;// 利潤和 totalProfit 在最大 k 個利潤的基礎上不會變大unordered_set<int> vis; // 判斷類別是否出現過stack<int> dup; // 重復類別的利潤,棧頂最小for (int i = 0, n = items.size(); i < n; ++i) {int profit = items[i][0], category = items[i][1];if (i < k) {totalProfit += profit;if (vis.count(category)) dup.push(profit);else vis.insert(category);} // 如果新添加的項目的類別之前選過了,則distinct_categories不會變大 else if (!dup.empty() && !vis.count(category)) {// 如果新添加的項目的類別之前沒有選過,distinct_categories^2可能變大vis.insert(category);// 我們移除最小利潤的項目// 如果移除的項目的類別只有1個,則distinct_categories-1+1,不變,但總利潤可能變小// 如果移除的項目的類別有多個,則distinct_categories+1,這種情況就是可行的totalProfit -= dup.top(); dup.pop(); // 移除掉一個重復且利潤最小的項目totalProfit += profit; // 本項目目前只出現了一次,不應加入dup中;且以后出現也不會被考慮}ans = max(ans, totalProfit + (long long)(vis.size() * vis.size()));}return ans;}
};
