135. 分发糖果

Problem: 135. 分发糖果

思路

本题可以采用分块处理的做法，因为我们可以观察到这样一个性质：

对于第i位，其之后有若干个连续位评分递减，到第j位为第一个不满足下一位小于j，那么如果第j位只有1个糖果，并且前面递增1个糖果，所分发的糖果是最小的。

而如果i大于前一位的评分，我们只需要保证i能比前一位多一个糖果即可。

因为题目对于相同评分的孩子的糖果数没有要求，我们就不必考虑相等的情况。

这样遍历完一次数组，我们就可以求出所有位置的糖果，把他们加起来就得到了答案。

空间复杂度O(1)做法

我们可以发现上述过程并不需要保存所有位置的糖果数，如果是递减的情况，我们就可以直接求出需要加上的糖果数；如果是递增的情况，我们只需要记录上一次的糖果数，看情况是否需要增加糖果即可。

复杂度

• 时间复杂度: $O(n)$：n为数组长度
• 空间复杂度: $O(n)$或$O(1)$。

Code

class Solution {
    public int candy(int[] ratings) 
        int i = 0;
        int n = ratings.length;
        int total = n;
        int values[] = new int[n];
        while (i < n) {
            int start = i;
            while (i < n - 1 && ratings[i + 1] < ratings[i]) {
                i++;
            }
            for (int j = i; j >= start; j--) {
                values[j] = i - j;
            }
            if (start > 0 && ratings[start - 1] < ratings[start]) {
                values[start] = Math.max(values[start], values[start - 1] + 1);
            }
            i++;
        }
        for (int j = 0; j < n; j++) {
            total += values[j];
        }
        return total;
    }
}

class Solution {
    public int candy(int[] ratings) {
        int i = 0;
        int n = ratings.length;
        int total = n;
        int pre = 0;
        while (i < n) {
            int start = i;
            while (i < n - 1 && ratings[i + 1] < ratings[i]) {
                i++;
            }
            for (int j = i; j >= start; j--) {
                total += i - j;
            }
            if (start > 0 && ratings[start - 1] < ratings[start]) {
                total += Math.max(0, pre + 1 - i + start);
                if (i == start) pre++;
                else {
                    pre = 0;
                }
            } else {
                pre = 0;
            }
            i++;
        }
        return total;
    }
}