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 但是难点是在看懂题目吧