輸入給定一個整數陣列,分別代表每小朋友的快樂值。
要求我們選擇其中最快樂的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 之間。
題目很明顯是要挑前k個最大的元素,
這個需求可以透過排序或者建造最大堆MaxHeap來滿足。
兩種解法都可以,最後複雜度也是同樣O( n log n )等級的。
有一個實作上的細節請留意,題目有額外特殊的規則,每挑一人,快樂值會遞減,一直扣到剩下零為止。
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
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
n個數值進行排序,所需時間為O( n log n)。
in-place排序,in-place建造最大堆,其他用到的都是固定尺寸的O(1)臨時變數。
挑前k個最大的元素,
這個需求可以透過排序或者建造最大堆MaxHeap來滿足。