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

[leetcode]Candy @ Python

2024-07-06 11:43:21   226人阅读

原题地址：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)

 


联系
我们