分发糖果

题目链接

135.分发糖果

解题思路

左右两次贪心

代码实现

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];

        // 每个孩子至少 1 个糖果
        for (int i = 0; i < n; i++) {
            candies[i] = 1;
        }

        // 从左往右：保证右边评分高时，右边糖果更多
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // 从右往左：保证左边评分高时，左边糖果更多
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        int sum = 0;
        for (int c : candies) {
            sum += c;
        }

        return sum;
    }
}

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(n)$