leetcode-135-Candy

发表于   |  

描述

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

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.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

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

Example 2:

1
2
3
4
Input: ratings = [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.

Constraints:

  • n == ratings.length
  • 1 <= n <= 2 * 104
  • 0 <= ratings[i] <= 2 * 104

分析

左边一次，右边一次，两次遍历即可。时间复杂度和空间复杂度都是 O(n), 如果记录递增，递减序列的长度，是可以在时间复杂度 O(1) 的情况下完成的。

解决方案1(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def candy(self, ratings: List[int]) -> int:
        ratingsLen = len(ratings)
        left = [0] * ratingsLen
        for i in range(ratingsLen):
            if i > 0 and ratings[i] > ratings[i-1]:
                left[i] = left[i-1] + 1
            else:
                left[i] = 1
                
        result = right = 0
        
        for i in range(ratingsLen-1, -1, -1):
            if i < ratingsLen - 1 and ratings[i] > ratings[i+1]:
                right += 1
            else:
                right = 1
            result += max(left[i], right)
        return result

相关问题

题目来源