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
• 从左到右扫一遍，使满足如果比左邻居高就大的条件
• 从右到左扫一遍，是满足如果比右邻居高就大的条件

Solution

class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        if not ratings:
            return 0
        length = len(ratings)    

        result = [1 for i in range(length)]

        for i in range(1, length):
            if ratings[i] > ratings[i-1]:
                result[i] = result[i-1] + 1

        for i in range(length-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                result[i] = max(result[i], result[i+1]+1)

        return sum(result)

Reference