ChunNote
0%

leetCode-135:Candy

发表于 分类于

问题描述

给定一个数组，表示每个小孩的排名，现在给小孩分配糖果，要求满足：每个小孩至少分到一个糖果，排名比旁边高的小孩分配到的糖果要多于旁边的小孩。求出分配的糖果数量总和最小的值。题目链接：**点我**

样例输入输出

输入：[1,0,2]

输出：5

解释：第一个小孩分配 2 个糖果，第二个小孩分配 1 个糖果，第三个小孩分配 2 个糖果

输入：[1,2,2]

输出：4

输出：第一个小孩分配 1 个糖果，第二个小孩分配 2 个糖果，第三个小孩分配 1 个糖果

问题解法

要让分配的糖果总数最小，就需要在每个人拥有一个糖果后，找出数组中的升序序列和降序序列，然后对这子序列的小孩的糖果数依次加一（升序序列：从左到右，依次加一；降序序列：从右到左，依次加一）。代码如下：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution
{
    public int candy(int[] ratings)
    {
        if (ratings == null || ratings.length == 0)
        {
            return 0;
        }

        if (ratings.length == 1)
        {
            return 1;
        }

        int begin = 0;
        int index = begin + 1;
        int sum = ratings.length;
        while (index < ratings.length)
        {
            // 找出升序序列
            while (index < ratings.length && ratings[index - 1] < ratings[index])
            {
                index++;
            }

            int top = index - 1;

            // 找出降序序列
            while (index < ratings.length && ratings[index - 1] > ratings[index])
            {
                index++;
            }

            if (top - begin > index - top - 1)
            {
                // top 放在升序序列中
                int ascendingLength = top - begin + 1;
                sum += ascendingLength * (ascendingLength - 1) / 2;

                int descendingLength = index - top - 1;
                sum += descendingLength * (descendingLength - 1) / 2;
            }
            else
            {
                // top 放在降序序列中
                int ascendingLength = top - begin;
                sum += ascendingLength * (ascendingLength - 1) / 2;

                int descendingLength = index - top;
                sum += descendingLength * (descendingLength - 1) / 2;
            }

            // 排名相等，不用额外分配糖果，直接跳过
            while (index < ratings.length && ratings[index - 1] == ratings[index])
            {
                index++;
            }
            begin = index - 1;
        }

        return sum;
    }
}