美文网首页
135. Candy

135. Candy

作者: codingXue | 来源:发表于2016-09-27 21:28 被阅读11次

    问题分析

    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?

    问题分析

    我想的思路超时了,于是到网上找了解题报告,具体做法为两遍遍历。首先从左向右遍历ratings数组,若本身比左邻居排名高,则将自身candy数设为左邻居值+1;然后从右向左遍历ratings数组,若本身比右邻居排名高,且当前candy没有比右邻居多,则将自身candy数设为右邻居值+1。

    AC代码

    class Solution(object):
        def candy(self, ratings):
            """
            :type ratings: List[int]
            :rtype: int
            """
            n = len(ratings)
            if n < 2:
                return n
            cd = [1 for i in range(n)]
            for i in range(1, n):
                if ratings[i] > ratings[i-1]:
                    cd[i] = cd[i-1] + 1
            for i in range(n-2, -1, -1):
                if ratings[i] > ratings[i+1] and cd[i] < cd[i+1] + 1:
                    cd[i] = cd[i+1] + 1
            return sum(cd)
    

    Runtime: 92 ms, which beats 65.71% of Python submissions.

    相关文章

      网友评论

          本文标题:135. Candy

          本文链接:https://www.haomeiwen.com/subject/joqhyttx.html