Candy

Problem: Candy

We first assume we give every child 1 candy. Then we check from the second that whether current child is rated higher than former one. If so, we make his or her candy one more than former's. By this, we can make sure children with a higher rating get more candies than their former children. Then we check from tail to head and do the same thing. We make sure current child with higher rate get one more candy than latter one's. Besides, we need to make sure former child with higher rate get at least one more candy than current one's. By two-way iteration, we can get the minimum candies.

Code in Python:

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