首页 > 代码库 > [leetcode]Candy @ Python

[leetcode]Candy @ Python

原题地址:https://oj.leetcode.com/problems/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?

解题思路:求最少的蛋糕数。先从前到后扫描一遍数组,如果序列递增,就+1;然后从后到前扫描一遍数组,序列递增,+1。保证最低谷(ratings最小)永远是1就可以了。

代码:

class Solution:
    # @param ratings, a list of integer
    # @return an integer
    def candy(self, ratings):
        candynum = [1 for i in range(len(ratings))]
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                candynum[i] = candynum[i-1] + 1
        for i in range(len(ratings)-2, -1, -1):
            if ratings[i+1] < ratings[i] and candynum[i+1] >= candynum[i]:
                candynum[i] = candynum[i+1] + 1
        return sum(candynum)