LeetCode——分发糖果

NO.135 分发糖果困难

思路一：贪心算法 分发糖果的规则：

如果[i]比[i-1]分高即右边的大于左边的，则[i]的糖果要比[i-1]的多，但是为了使总糖果数最少，所以给[i]增加最小的增量 +1。
同理，如果[i]比[i+1]分高即左边的大于右边的，则[i]的糖果要比[i+1]的多，但是为了使总糖果数最少，所以给[i]增加最小的增量 +1。

只有当必须给某个孩子增加糖果时(左大于右/右大于左)，才给这个孩子增加一个最小的增量 +1。

开始，每个人都分配最少的糖果 1 个。先从左向右遍历孩子的分数，如果[i]>[i-1]则使[i]的糖果=[i-1]的糖果+1，并将这一过程中每个人分配的糖果数量记录在 left 数组中。

同理，再从逆序遍历孩子的分数，如果[i]>[i+1]则使[i]的糖果=[i+1]的糖果+1，并将这一过程中每个人分配的糖果数量记录在 right 数组中。

最后，计算总糖果时，每个人应得的糖果数是取 left 或 right 中对应的最大糖果数，这样才能同时满足开头的两个规则。

public int candy(int[] ratings) {
    int[] left = new int[ratings.length];
    int[] right = new int[ratings.length];
    //初始化每人最少一个糖
    Arrays.fill(left, 1);
    Arrays.fill(right, 1);
    //顺序遍历,按照规则一进行分配
    for (int i = 1; i < ratings.length; i++) {
        if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
    }
    //逆序遍历,按照规则二进行分配
    for (int i = ratings.length - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
    }
    //统计所有孩子的糖果
    int sum = 0;
    for (int i = 0; i < ratings.length; i++) {
        //每个孩子按照,规则一和规则二中相应最大的数字进行分配
        sum += Math.max(left[i], right[i]);
    }
    return sum;
}

时间复杂度：O(n) 五次遍历。

空间复杂度：O(n) 两个数组记录，两个规则下的分配方案。

这个思路还能再优化一下，只用一个数组 candies 。第一次遍历不变，第二次遍历时如果ratings[i] > ratings[i + 1]不立刻更新，如果此时 candies[i] 已经大于 candies[i+1]则不需要更新，否则更新为 candies[i+1]+1，并且到此已经完成了对 candies[i] 的分配，直接统计入结果中即可。

public int candy(int[] ratings) {
    int[] candies = new int[ratings.length];
    //初始化
    candies[0] = 1;
    //顺序遍历
    for (int i = 1; i < ratings.length; i++) {
        //分数大于前面的孩子,则多一个糖
        if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
        //否则1个
        else candies[i] = 1;
    }
    //注意不要漏统计最后一个孩子
    int sum = candies[candies.length - 1];
    for (int i = ratings.length - 2; i >= 0; i--) {
        //只有当左大于右,且左孩子的糖少于右孩子时才更新
        if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        //统计
        sum += candies[i];
    }
    return sum;
}

时间复杂度：O(n) 两次遍历。

空间复杂度：O(n) 一个数组记录。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.135 分发糖果 困难

NO.135 分发糖果困难