Kids With the Greatest Number of Candies
題目描述
給定陣列 candies 和整數 extraCandies，回傳布林陣列，表示每個孩子加上 extraCandies 後是否能擁有最多糖果。
輸入：candies = [2,3,5,1,3], extraCandies = 3
輸出：[true,true,true,false,true]
輸入：candies = [4,2,1,1,2], extraCandies = 1
輸出：[true,false,false,false,false]
解題思路
1
找最大值
用一次 O(n) 掃描找出 candies 中的最大值 maxCandy，作為門檻
2
逐一比較
第二次遍歷，對每個 candies[i] 計算 candies[i] + extraCandies，若 ≥ maxCandy 則為 true
3
回傳結果
收集所有布林值組成結果陣列，長度與 candies 相同
程式碼
C#
csharp
public class Solution {
public IList<bool> KidsWithCandies(int[] candies, int extraCandies) {
int maxCandy = candies.Max();
return candies.Select(c => c + extraCandies >= maxCandy).ToList();
}
}TypeScript
typescript
function kidsWithCandies(candies: number[], extraCandies: number): boolean[] {
const maxCandy = Math.max(...candies);
return candies.map(c => c + extraCandies >= maxCandy);
}Python
python
def kidsWithCandies(candies: list[int], extraCandies: int) -> list[bool]:
max_candy = max(candies)
return [c + extraCandies >= max_candy for c in candies]複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(n) |
找最大值需遍歷一次 O(n)，逐一比較再遍歷一次 O(n)，合計 O(2n) = O(n)。輸出陣列與輸入等長，空間 O(n)。
邊界情況
- 所有孩子糖果數相同：例如
[5,5,5],extraCandies=0，每個孩子加上 0 後仍等於最大值 5，全部為 true - extraCandies = 0：只有原本就是最大值的孩子才會是 true
- 只有一個孩子：該孩子一定是最多的，回傳
[true]
圖解
candies: [2,3,5,1,3]
掃描一遍→
maxCandy = 5
以 5 為門檻→
逐一比較 c+3 >= 5
產生結果→
[true,true,true,false,true]
圖表展示兩步驟流程：第一步掃描找到 maxCandy=5，第二步以 5 為門檻逐一判斷。例如 candies[0]=2+3=5 ≥ 5 為 true，candies[3]=1+3=4 不足 5 為 false。
進階觀點
💡面試追問
- 如果 extraCandies 可以分給不同孩子？ 那就變成 combinatorial optimization 問題，需要考慮所有分配方式。若要最大化滿足條件的孩子數，可以用 greedy：優先把糖果分給差距最小的孩子。
- 能否一次遍歷完成？ 不行。必須先知道 maxCandy 才能判斷，而 maxCandy 要掃完整個陣列才知道，所以至少需要兩次遍歷。排序可以一次得到最大值但代價是 O(n log n)，不划算。
- 這題的本質？ 就是一個 threshold 判斷。核心 insight 是：額外糖果只給一個孩子，所以只需跟全局最大值比較，不需考慮其他孩子的變化。
理解測驗
🤔 為什麼只需要跟最大值比較就能判斷？
🤔 這題的時間複雜度能比 O(n) 更好嗎？