題目敘述
輸入給定一個整數陣列，分別代表每小朋友的快樂值。
要求我們選擇其中最快樂的k位小朋友，累加這群小朋友的快樂值。
有一個特殊的規則，第一位選中的小朋友快樂值不變。
接著，第二位選中的小朋友快樂值-1
再接著，第三位選中的小朋友快樂值-2
快樂值扣到只剩下0就不再往下扣
...其餘依此類推
輸出時整數返回答案。
測試範例
Example 1:
Input: happiness = [1,2,3], k = 2
Output: 4
Explanation: We can pick 2 children in the following way:
- Pick the child with the happiness value == 3. The happiness value of the remaining children becomes [0,1].
- Pick the child with the happiness value == 1. The happiness value of the remaining child becomes [0]. Note that the happiness value cannot become less than 0.
The sum of the happiness values of the selected children is 3 + 1 = 4.
Example 2:
Input: happiness = [1,1,1,1], k = 2
Output: 1
Explanation: We can pick 2 children in the following way:
- Pick any child with the happiness value == 1. The happiness value of the remaining children becomes [0,0,0].
- Pick the child with the happiness value == 0. The happiness value of the remaining child becomes [0,0].
The sum of the happiness values of the selected children is 1 + 0 = 1.
Example 3:
Input: happiness = [2,3,4,5], k = 1
Output: 5
Explanation: We can pick 1 child in the following way:
- Pick the child with the happiness value == 5. The happiness value of the remaining children becomes [1,2,3].
The sum of the happiness values of the selected children is 5.
約束條件
Constraints:
1 <= n == happiness.length <= 2 * 10^5
小朋友的總數介於1~二十萬 之間。
1 <= happiness[i] <= 10^8
每味小朋友的快樂值介於1~一億 之間。
1 <= k <= n
k值介於 1 ~ n 之間。
演算法 排序 或 最大堆MaxHeap
題目很明顯是要挑前k個最大的元素，
這個需求可以透過排序或者建造最大堆MaxHeap來滿足。
兩種解法都可以，最後複雜度也是同樣O( n log n )等級的。
有一個實作上的細節請留意，題目有額外特殊的規則，每挑一人，快樂值會遞減，一直扣到剩下零為止。
程式碼 排序 或 最大堆MaxHeap
class Solution:
def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
happiness.sort( reverse = True )
summation = 0
for i in range(k):
summation += max(happiness[i] - i, 0)
return summation
程式碼 最大堆MaxHeap
class Solution:
def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
heapq._heapify_max(happiness)
summation = 0
for i in range(k):
cur_largest = heapq._heappop_max(happiness)
summation += max(cur_largest - i, 0)
return summation
複雜度分析
時間複雜度: O(n log n)
n個數值進行排序，所需時間為O( n log n)。
空間複雜度: O(1)
in-place排序，in-place建造最大堆，其他用到的都是固定尺寸的O(1)臨時變數。
關鍵知識點
挑前k個最大的元素，
這個需求可以透過排序或者建造最大堆MaxHeap來滿足。
