LeetCode 筆記 - 135. Candy

Posted on

題目在此 135. Candy

給一個數列，代表一系列小孩的排名，有以下規則

  • 每個小孩至少一顆糖果
  • 如果小孩對他的鄰居有更高的排名，必須比他的鄰居拿更多的糖果

請計算最少可以給幾顆？

解題思維

這題是一題 Hard problem，但解題思緒雖然崎嶇了點，但沒有太複雜

依正常情況，糖果的分佈勢必會呈現一個山形，而山頂的數量必定是由左邊或右邊的山決定的
這裡有一點可以注意的是左邊山坡跟右邊的山坡是獨立沒有關係的

因此我們可以分開計算左右山坡，最後在計算山頂的數字即可 max(左邊, 右邊)

程式碼

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

        return result

相關文章