【刷题篇】分发糖果_分糖果问题2 java算法

一、题目

OJ链接

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

二、题解

2.1初阶分糖果

思路：

源码：

public static int candy1(int[] ratings) {
        if(ratings==null||ratings.length==0){
            return 0;
        }
        int N= ratings.length;
        int[] left=new int[N];
        left[0]=1;
        for (int i = 1; i < N; i++) {
            if(ratings[i]>ratings[i-1]){
                left[i]=left[i-1]+1;
            }else {
                left[i]=1;
            }
        }
        int[] right=new int[N];
        right[N-1]=1;
        for (int i = N-2; i >=0; i--) {
            if(ratings[i]>ratings[i+1]){
                right[i]= right[i+1]+1;
            }else {
                right[i]=1;
            }
        }
        int ans=0;
        for (int i = 0; i < N; i++) {
            ans+=Math.max(left[i],right[i] );
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

2.2进阶分糖果

在初阶的基础上加了一个要求：

• 相邻的孩子如果分数一样，得到的糖果数也必须一样

思路：
在初阶解题的基础上，加一个判断条件即可：

1.从前往后遍历时，如果[i]==[i-1],则i号的得到的糖果数和i-1一样

2.从后往前遍历时，如果[i]==[i+1],则i号的得到的糖果数和i+1一样

public static int candy2(int[] ratings) {
        if(ratings==null||ratings.length==0){
            return 0;
        }
        int N= ratings.length;
        int[] left=new int[N];
        left[0]=1;
        for (int i = 1; i < N; i++) {
            if(ratings[i]>ratings[i-1]){
                left[i]=left[i-1]+1;
            }else if(ratings[i]==ratings[i-1]){
                left[i]=left[i-1];
            } else {
                left[i]=1;
            }
        }
        int[] right=new int[N];
        right[N-1]=1;
        for (int i = N-2; i >=0; i--) {
            if(ratings[i]>ratings[i+1]){
                right[i]= right[i+1]+1;
            }else if(ratings[i]==ratings[i-1]) {
                right[i] = right[i + 1];
            }else {
                right[i]=1;
            }
        }
        int ans=0;
        for (int i = 0; i < N; i++) {
            ans+=Math.max(left[i],right[i] );
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33