?基于官方題解，進(jìn)行補(bǔ)充說明

給你一個(gè)長(zhǎng)度為?n?的二維整數(shù)數(shù)組?items?和一個(gè)整數(shù)?k?。

items[i] = [profiti, categoryi]，其中?profiti?和?categoryi?分別表示第?i?個(gè)項(xiàng)目的利潤(rùn)和類別。

現(xiàn)定義?items?的?子序列?的?優(yōu)雅度?可以用?total_profit + distinct_categories2?計(jì)算，其中?total_profit?是子序列中所有項(xiàng)目的利潤(rùn)總和，distinct_categories?是所選子序列所含的所有類別中不同類別的數(shù)量。

你的任務(wù)是從?items?所有長(zhǎng)度為?k?的子序列中，找出?最大優(yōu)雅度?。

用整數(shù)形式表示并返回?items?中所有長(zhǎng)度恰好為?k?的子序列的最大優(yōu)雅度。

注意：數(shù)組的子序列是經(jīng)由原數(shù)組刪除一些元素（可能不刪除）而產(chǎn)生的新數(shù)組，且刪除不改變其余元素相對(duì)順序。

示例 1：

輸入：items = [[3,2],[5,1],[10,1]], k = 2
輸出：17
解釋：
在這個(gè)例子中，我們需要選出長(zhǎng)度為 2 的子序列。
其中一種方案是 items[0] = [3,2] 和 items[2] = [10,1] 。
子序列的總利潤(rùn)為 3 + 10 = 13 ，子序列包含 2 種不同類別 [2,1] 。
因此，優(yōu)雅度為 13 + 22 = 17 ，可以證明 17 是可以獲得的最大優(yōu)雅度。 

示例 2：

輸入：items = [[3,1],[3,1],[2,2],[5,3]], k = 3
輸出：19
解釋：
在這個(gè)例子中，我們需要選出長(zhǎng)度為 3 的子序列。 
其中一種方案是 items[0] = [3,1] ，items[2] = [2,2] 和 items[3] = [5,3] 。
子序列的總利潤(rùn)為 3 + 2 + 5 = 10 ，子序列包含 3 種不同類別 [1, 2, 3] 。 
因此，優(yōu)雅度為 10 + 32 = 19 ，可以證明 19 是可以獲得的最大優(yōu)雅度。

示例 3：

輸入：items = [[1,1],[2,1],[3,1]], k = 3
輸出：7
解釋：
在這個(gè)例子中，我們需要選出長(zhǎng)度為 3 的子序列。
我們需要選中所有項(xiàng)目。
子序列的總利潤(rùn)為 1 + 2 + 3 = 6，子序列包含 1 種不同類別 [1] 。
因此，最大優(yōu)雅度為 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：用于記錄當(dāng)前子序列中出現(xiàn)的不同類別。

   • profit：記錄當(dāng)前子序列的總利潤(rùn)。

   • res：記錄最大的優(yōu)雅度。

   • st：用來記錄那些在子序列中出現(xiàn)了多次的類別的項(xiàng)目的利潤(rùn)。

2. 排序：首先按利潤(rùn)從高到低對(duì)項(xiàng)目進(jìn)行排序。這樣可以確保我們?cè)谶x擇前 k 個(gè)項(xiàng)目時(shí)，總利潤(rùn)是最大的。

3. 遍歷項(xiàng)目：對(duì)排序后的項(xiàng)目進(jìn)行遍歷。

   • 如果當(dāng)前項(xiàng)目在前 k 個(gè)范圍內(nèi)（即子序列還沒有達(dá)到長(zhǎng)度 k）：

     • 將其利潤(rùn)加入 profit。

     • 將其類別加入 categorySet，如果類別已經(jīng)存在，則將利潤(rùn)壓入 st 堆棧中。

   • 如果當(dāng)前項(xiàng)目在 k+1 項(xiàng)目之后（即子序列已經(jīng)達(dá)到長(zhǎng)度 k），并且 st 堆棧不為空，且當(dāng)前項(xiàng)目的類別不在 categorySet 中：

     • 從 st 中彈出一個(gè)利潤(rùn)最小的項(xiàng)目，用當(dāng)前項(xiàng)目替換它，增加 profit 和 categorySet。

4. 計(jì)算優(yōu)雅度：在每次更新 profit 和 categorySet 后，計(jì)算當(dāng)前優(yōu)雅度，并更新最大優(yōu)雅度 res。

主要邏輯解釋

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

   • 這個(gè)步驟確保我們優(yōu)先選擇利潤(rùn)高的項(xiàng)目，以保證前 k 個(gè)項(xiàng)目的總利潤(rùn)最大。

2. 前 k 項(xiàng)目：

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

   • 對(duì)于前 k 個(gè)項(xiàng)目，直接將利潤(rùn)加入總利潤(rùn) profit。

   • 將項(xiàng)目的類別加入 categorySet，如果類別已經(jīng)存在，則將利潤(rùn)壓入 st 堆棧中。

3. 替換邏輯：

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

   • 對(duì)于第 k+1 項(xiàng)目之后的項(xiàng)目，如果 st 堆棧不為空，且當(dāng)前項(xiàng)目的類別不在 categorySet 中：

     • 從 st 中彈出一個(gè)利潤(rùn)最小的項(xiàng)目，并用當(dāng)前項(xiàng)目替換它。這樣確保增加新的類別，同時(shí)總利潤(rùn)減少最少。

4. 計(jì)算優(yōu)雅度：

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

   • 每次更新 profit 和 categorySet 后，計(jì)算當(dāng)前優(yōu)雅度，并更新最大優(yōu)雅度 res。

代碼

class Solution {// 初始化變量Set<Integer> categorySet = new HashSet<>(); // 用于記錄當(dāng)前子序列中出現(xiàn)的不同類別long profit = 0; // 當(dāng)前子序列的總利潤(rùn)long res = 0; // 記錄最大的優(yōu)雅度Deque<Integer> st = new ArrayDeque<>(); // 記錄重復(fù)類別項(xiàng)目的利潤(rùn)public long findMaximumElegance(int[][] items, int k) {// 按利潤(rùn)從高到低排序Arrays.sort(items, (item0, item1) -> item1[0] - item0[0]);for (int i = 0; i < items.length; i++ ) {if (i < k) {// 在前 k 個(gè)項(xiàng)目中// 將項(xiàng)目的利潤(rùn)加入總利潤(rùn)profit += items[i][0];if (!categorySet.add(items[i][1])) {// 如果類別已經(jīng)存在于 categorySet 中，將利潤(rùn)壓入堆棧。以便后面替換st.push(items[i][0]);}} else if (!st.isEmpty() && categorySet.add(items[i][1])) {// 在第 k+1 項(xiàng)目及之后，并且當(dāng)前項(xiàng)目的類別不在 categorySet 中// 且堆棧不為空時(shí)，進(jìn)行替換操作// 用當(dāng)前項(xiàng)目替換利潤(rùn)最小的重復(fù)類別項(xiàng)目profit += items[i][0] - st.pop();}// 計(jì)算當(dāng)前優(yōu)雅度并更新最大優(yōu)雅度res = Math.max(res, profit + (long)categorySet.size() * categorySet.size());}// 返回最大優(yōu)雅度return res;}
}

詳解 st 隊(duì)列

st 的作用是在處理項(xiàng)目時(shí)，用于記錄那些在子序列中類別出現(xiàn)重復(fù)的項(xiàng)目的利潤(rùn)。具體來說，當(dāng) st 不為空且當(dāng)前項(xiàng)目的類別與已選子序列中的所有類別都不相同時(shí)，可以通過從 st 彈出一個(gè)利潤(rùn)最小的項(xiàng)目，用當(dāng)前項(xiàng)目替換它，從而增加不同類別的數(shù)量，并盡量減少總利潤(rùn)的減少。下面是更詳細(xì)的解釋：

st 的作用

1. 記錄重復(fù)類別的項(xiàng)目利潤(rùn)：當(dāng)一個(gè)項(xiàng)目的類別在子序列中已經(jīng)存在時(shí)，將其利潤(rùn)值記錄到 st 中。這是因?yàn)檫@些項(xiàng)目不會(huì)增加不同類別的數(shù)量，但它們的利潤(rùn)可能在后續(xù)處理中被替換掉。

2. 替換以增加不同類別的數(shù)量：在處理第 k+1 個(gè)及之后的項(xiàng)目時(shí)，如果當(dāng)前項(xiàng)目的類別不在已選子序列的類別集合 categorySet 中，并且 st 不為空，可以將當(dāng)前項(xiàng)目的利潤(rùn)與 st 中最小的利潤(rùn)值進(jìn)行替換，從而增加不同類別的數(shù)量并盡量保持總利潤(rùn)的最大化。

詳細(xì)解釋

假設(shè)我們當(dāng)前已經(jīng)選擇了前 k 個(gè)項(xiàng)目，這時(shí) categorySet 中記錄了這些項(xiàng)目的類別。如果其中某些類別重復(fù)了，那么這些重復(fù)類別項(xiàng)目的利潤(rùn)將被壓入 st。當(dāng)我們處理第 k+1 個(gè)及之后的項(xiàng)目時(shí)：

1. 如果當(dāng)前項(xiàng)目的類別不在 categorySet 中，且 st 不為空：

   • 我們可以將 st 中最小的利潤(rùn)值彈出，并用當(dāng)前項(xiàng)目替換它。這樣做有兩個(gè)好處：

     • 增加不同類別的數(shù)量。

     • 盡量減少總利潤(rùn)的減少，因?yàn)槲覀冞x擇了 st 中最小的利潤(rùn)值進(jìn)行替換。

代碼示例中的 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 個(gè)項(xiàng)目：

   • profit += items[i][0];：將利潤(rùn)加到總利潤(rùn)中。

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

     • 如果項(xiàng)目類別已經(jīng)存在于 categorySet 中，將其利潤(rùn)值壓入 st。

2. 處理第 k+1 個(gè)及之后的項(xiàng)目：

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

     • 如果當(dāng)前項(xiàng)目的類別不在 categorySet 中，且 st 不為空，彈出 st 中最小的利潤(rùn)值（假設(shè) st 是一個(gè)優(yōu)先隊(duì)列，能夠快速獲得最小值），并用當(dāng)前項(xiàng)目的利潤(rùn)替換它。