題目

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

解釋題目

題目會給一個 ratings 的陣列，每個指標代表一個學生，其值代表權種。需要依照權重發放糖果，發放的規則須符合以下兩點

  1. 每個小孩至少要拿到一顆糖果
  2. 相鄰的小孩，權重高的拿到的糖果數量要多於權重低的
    要注意的是，權重一樣的，糖果數量不一定要相同，可以是一顆就好。這題要求發放最少的糖果數量。

思路

  1. 先假設一開始的糖果數是 [1] * len(ratings)
  2. 這題一開始很好想，就是 由左到右 遍歷一遍，如果遇到權重大的，糖果數就加一個。但是，如果遇到像是中間權重最低的，如 [1, 0, 2]，就要往前回補糖果。因此，這題的核心就是要分成兩段遍歷，一段是由左到右，另一段是由右到左。
  3. 由右到左的話也是一樣概念，遇到權重大的也是要加一顆糖果。不過要注意的是，因為已經由左到右遍歷過，所以有些小孩的糖果已經是達標的最低數量，所以由右到左遍歷時，要取 candy[i-1] 跟 candy[i] + 1 的最大值，以免把原本正確的糖果數覆蓋變少。基本上只會覆蓋變少不會變多，所以要取最大值。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candy = [1] * n

        # 左到右
        for i in range(n - 1):
            if ratings[i + 1] > ratings[i]:
                candy[i + 1] = candy[i] + 1

        # 右到左
        for i in range(n - 1, 0, -1):
            if ratings[i - 1] > ratings[i]:
                candy[i - 1] = max(candy[i - 1], candy[i] + 1)
        
        return sum(candy)