題目在此 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
|
也許你也會想看看