https://youtu.be/KxNII3csgw4
135. Candy
有 n 個孩子站成一排。每個孩子都被分配一個在整數數組 ratings 中給出的評級值。
您向這些兒童贈送糖果需符合以下要求：
- 每個孩子必須至少擁有一顆糖果。
- 評分較高的孩子比鄰居獲得更多醣果。
返回將糖果分發給孩子們所需的最少糖果數量。
Topics: Array, Greedy
這題有兩種解法
簡單解法是跑兩遍for loop
一次forward 一次backward
forward pass 每看到一個上升rating就加多一個糖果
backward pass 也是有上升就加多一個糖果
(視情況可以不加 開多一個candies array 儲存那個屁孩forward時拿多少
backward時如果發現屁孩本來手上就夠多糖果就不用加糖果給他)
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
candies = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i-1]:
candies[i] = candies[i-1] + 1
for i in range(n-2, -1, -1):
if ratings[i] > ratings[i+1]:
candies[i] = max(candies[i], candies[i+1] + 1)
return sum(candies)
困難解法是跑一遍forward pass就好
因為題目只要求總糖果量
所以其實就每看到一次上升或下降負荷就塞多一個糖果
用up和down兩個變數來記錄累積的上升負荷和下降負荷
你就想像一個小山丘 山丘越高 累積的up和down越多 糖果累加也越多
class Solution:
def candy(self, ratings: List[int]) -> int:
if not ratings:
return 0
ret, up, down, peak = 1, 0, 0, 0
for prev, curr in zip(ratings[:-1], ratings[1:]):
if prev < curr:
up, down, peak = up + 1, 0, up + 1
ret += 1 + up
elif prev == curr:
up = down = peak = 0
ret += 1
else:
up, down = 0, down + 1
ret += down + int(peak < down)
return ret
雖然這題說是HARD 但是難點是在看懂題目吧