Leetcode解题-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?

分析

有一定难度。对于某个位置i上的小孩，它的糖果数取决于他自己和左右邻居的关系。设ratings数组为R，分配给小孩的糖果数为数组C。我们可以这样来考虑这个问题，拆分为两个步骤：

  1. 首先，如果只要求C[i] > C[i-1] iff R[i] > R[i-1]，也就是说只考虑每个小孩左手边的小孩，那么如果R[i] > R[i-1]则C[i] = C[i-1] + 1，否则C[i] = 1。
  2. 然后我们再考虑加上右手边小孩的限制，如果R[i] > R[i+1]，则C[i] = max(C[i+1] + 1, C[i])。

这样一来，考虑到上面被分解的两个问题内部的互相依赖情况，我们就可以用两个循环分别从左到右、从右到左遍历数组，得到时间O(n)，空间O(n)的算法。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def candy(self, R):
        """
        :type R: List[int]
        :rtype: int
        """
        n = len(R)
        C = [1] * n
        for i in xrange(1, n):
            if R[i] > R[i - 1]:
                C[i] = C[i - 1] + 1

        for i in xrange(n - 2, -1, -1):
            if R[i] > R[i + 1]:
                C[i] = max(C[i + 1] + 1, C[i])

        return sum(C)

热评文章