【LC75】No1431. 拥有最多糖果的孩子

题目描述

有 n 个有糖果的孩子。给你一个数组 candies，其中 candies[i] 代表第 i 个孩子拥有的糖果数目，和一个整数 extraCandies 表示你所有的额外糖果的数量。

返回一个长度为 n 的布尔数组 result，如果把所有的 extraCandies 给第 i 个孩子之后，他会拥有所有孩子中 最多 的糖果，那么 result[i] 为 true，否则为 false。

注意，允许有多个孩子同时拥有 最多 的糖果数目。

示例

示例 1：

输入：candies = [2,3,5,1,3], extraCandies = 3
输出：[true,true,true,false,true] 
解释：如果你把额外的糖果全部给：
孩子 1，将有 2 + 3 = 5 个糖果，是孩子中最多的。
孩子 2，将有 3 + 3 = 6 个糖果，是孩子中最多的。
孩子 3，将有 5 + 3 = 8 个糖果，是孩子中最多的。
孩子 4，将有 1 + 3 = 4 个糖果，不是孩子中最多的。
孩子 5，将有 3 + 3 = 6 个糖果，是孩子中最多的。

示例 2：

输入：candies = [4,2,1,1,2], extraCandies = 1
输出：[true,false,false,false,false] 
解释：只有 1 个额外糖果，所以不管额外糖果给谁，只有孩子 1 可以成为拥有糖果最多的孩子。

示例 3：

输入：candies = [12,1,12], extraCandies = 10
输出：[true,false,true]

链接

思路

最符合我的一集！(自信上前

非常简单的一道题！

首先依旧是翻译题目，有一个元素全为整数的数组 candies，现在有一个整数 extraCandies，依次判断 candies 的每个元素加上 extraCandies 之后的值是否是数组中的最大值（每次只有一个元素与 extraCandies 相加），是则记录 true，否则记录 false，并将对应结果依次存储在一个布尔数组中返回。

既然是判断求和之后的值是否是数组中的最大值，那么可以简化为判断求和之后的值，与数组最大值之间的大小关系即可。

解法：直接遍历

先遍历数组，求出数组所有元素中的最大值。

之后再遍历一次数组，依次判断每个元素求和之后的值和此最大值的大小关系，记录在结果数组中。

思考了很久一次遍历能否解决，目前暂时没想到orz

代码

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int len = candies.length;
        int maxNum = candies[0];
        // 获得数组中的最大值
        for (int i = 0; i < len; i++) {
            maxNum = Math.max(maxNum, candies[i]);
        }
        // 判断每个元素加上extraCandies之后和最大值的大小，存入结果数组
        List<Boolean> res = new ArrayList();
        for (int j = 0; j < len; j++) {
            res.add(candies[j] + extraCandies >= maxNum);
        }
        return res;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)