leetcode135-- 分糖问题

leetcode135-- 分糖问题

题目

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?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.



题目的意思就是说有一些小朋友,每个小朋友手上有个权,然后现在需要给他们发糖,要保证每个人至少有一个糖,并且如果小朋友手里的权比较大的话,那他得到的糖果的数目要比他两边的人要多,但是如果只是相等的话,他就可能得不到那么多的了,像上面的第二个例子.

解法1

可以用两次遍历来解决,先把他们手里的糖果全部都初始化为1, 然后第一次遍历的话,如果右边的小朋友的较高的话,就让他的比他左边的多一个,

然后第二次从左边遍历,如果左边的权比较高的话, 他至少应该比右边的多一个,但是如果他已经高了的话就不用加了

所以应该取最大的那个,即

class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        res = 0
        n = len(ratings)
        nums = [1]*n
        
        # 第一次遍历,如果右边的权要大的话,就让他的比左边的多一个
        for i in range(n-1):
            if ratings[i+1] > ratings[i]:
                nums[i+1] = nums[i]+1
                
        # 第二次遍历,如果左边的比较高的话,这时候要看需不需要给他加了
        for i in range(n-1, 0, -1):
            if ratings[i-1] > ratings[i]:
                nums[i-1] = max(nums[i-1], nums[i]+1)
                
        return sum(nums)
                

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦