[LeetCode]135. Candy

Loading...

分数高的分的糖果要比两边的多，每人最少一个，求最少糖果数

最优解：

记录连续下降长度down以及下降开头位置prev，如果down >= prev，说明下降的结尾糖果数小于等于零了，就把prev删掉，将prev+down的下降序列替换成结尾为1的降序序列

public class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) {
            return 0;
        }
        int res = 1;
        int down = 0;
        int prev = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                if (down > 0) {
                    res += (down + 1) * down / 2;
                    if (prev <= down) {
                        res += down + 1 - prev;
                    }
                    prev = 1;
                    down = 0;
                }
                prev = ratings[i] == ratings[i - 1] ? 1 : prev + 1;
                res += prev;
            } else {
                down++;
            }
        }
        if (down > 0) {
            res += (down + 1) * down / 2;
            if (prev <= down) {
                res += down + 1 - prev;
            }
        }
        return res;
    }
}

时空复杂度均为O(n)解法：

从左到右遍历，保证与左侧邻居关系满足；再从右向左遍历，保证与右侧关系满足同时不破坏左侧关系（用max）

// 从左到右遍历，保证与左侧邻居关系满足；再从右向左遍历，保证与右侧关系满足同时不破坏左侧关系（用max）
// 遍历比较时，需要拿当前位置比较【前一个已经遍历到的位置】，保证已经计算出的结果不会错乱！！
public class Solution {
    public int candy(int[] ratings) {
        int res = 0;
        int[] candy = new int[ratings.length];
        Arrays.fill(candy, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }
        }
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candy[i] = Math.max(candy[i], candy[i + 1] + 1);
            }
        }
        for (int c : candy) {
            res += c;
        }
        return res;
    }
}