FlareBall's Blog
0%

135.分发糖果

Posted on Edited on In ,

贪心

题目要求相邻的孩子较多一方那个获得更多糖果，也就是说糖果发放取决于数组走势（上升or下降），因此可以将数组分为若干相似得山峰并分组求解，每座山中从两端山脚开始糖果依次递增，最多糖果为山峰。

双向遍历，分别满足山峰大于左边和山峰大于右边即可。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

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

也可以考虑一次遍历，考虑可能出现共享波谷，如1 4 5 2 0 1 4 5 2 中的0，他应该分应1颗糖果，如果直接统计1 4 5 2 0和 0 1 4 5 2两座山会导致0分配1颗糖果重复计算，所以事先为每人先分1颗糖果，这样在分组求解时山脚分0颗即可，避免了重复计算。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length, ans = n;  // 每人先分一颗
        for (int i = 0; i < n; ++i) {
            int start = i > 0 && ratings[i - 1] < ratings[i] ? i - 1 : i;
            while (i + 1 < n && ratings[i] < ratings[i + 1]) { // 严格递增段
                i++;
            }
            int top = i;
            while (i + 1 < n && ratings[i] > ratings[i + 1]) { // 严格递减段
                i++;
            }
            int increase = top - start;  // 严格递增得步数
            int decrease = i - top;  // 严格递减得步数
            int num1 = increase * (0 + increase - 1) / 2;
            int num2 = decrease * (decrease - 1 + 0) / 2;
            ans += num1 + num2 + Math.max(increase, decrease);
        }
        return ans;
    }
}