快樂崇拜 小朋友的快樂值 Leetcode #3075

Senjuti Kundu on Unsplash

題目敘述

輸入給定一個整數陣列，分別代表每小朋友的快樂值。

要求我們選擇其中最快樂的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來滿足。

Reference

[1] Maximize Happiness of Selected Children - LeetCode