卖萌的弱渣

I am stupid, I am hungry.

Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give?

Solution

  • 贪心算法，从左，从右扫描两次，当rating[i]大于相邻孩子j且糖果candies[i]少于candies[j]时，增加candies[i]
(Candy.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """

        n = len(ratings)
        if n == 0:
            return 0
        candies = [1] * (n)
        for i in range(1,n):

            if ratings[i] > ratings[i-1] and candies[i] <= candies[i-1]:
                candies[i] = candies[i-1]+1

        for i in range(n-2,-1,-1):
            if ratings[i] > ratings[i+1] and candies[i] <= candies[i+1]:
                candies[i] = candies[i+1]+1
        return sum(candies)