1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int candy(int[] ratings) {
        if (ratings.length == 0) {
            return 0;
        }
        int[] ans = new int[ratings.length];
        Arrays.fill(ans, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                ans[i] = ans[i - 1] + 1;
            }
        }
        int result = ans[ans.length - 1];
        for (int i = ans.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                ans[i] = Math.max(ans[i], ans[i + 1] + 1);
            }
            result += ans[i];
        }
        return result;
    }
}

关键就是找到递增和递减的区间是什么. 递增的话从最小到最大挨个加1即可. 但问题就出现在区间的两端, 如果左侧之前是平的, 那左侧可以从1开始就行. 如果左侧之前是递减到达, 那么左侧这里也可以是1. 右侧的话如果接下来是平的, 那没问题; 如果接下来要递减, 我们就要看递减的区间长度是多少. 如果比递增的区间长度长, 右侧端点的值要按这个递减区间长度来确定.

比如[5, 6, 7, 6, 5, 4, 3] 假设这是ratings, 那么在[0, 2]这个区间, 是递增的. 我们发糖那就是1, 2, 3发就行. 但是注意[2, 6]又构成递减区间, 此时我们从3从右到左发糖就是1, 2, 3, 4, 5. 此时7这个位置需要发5颗糖. 之前递增区间在7处发的是3颗糖, 我们要取最大值才能满足我们的题意, 也就是给rating是7的这个小朋友发5颗糖才行.

关键就在于递增递减. 递增的起始端点的糖是1, 递减的终止端点的糖是1. 然后根据区间长度来去不停的 + 1发糖. 如果遇到平的, 那就是发1颗糖即可.

但是只要被包含在递增或递减区间内的, 就必须按照我们之前讨论的那样去来.

上面的解法就是从左到右只看递增的区间, 看每个位置应该发多少糖满足题意. 然后从右往左看, 也是只看递增的区间, 按照我们的逻辑去发糖. 到最后我们取两次结果中每个位置的最大值, 这个值就能满足题意.

关键在于确定递增和递减区间.

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