LeetCode问题135糖果一次求解法求给每个孩子的糖果数量

Question

problem（https://leetcode.com/problems/candy/description/）语句如下：

有N个孩子站成一排。为每个子级分配一个评等值。您给这些符合以下要求的儿童糖果：

而只给出糖果的总数。我希望修改解决方案，以输出给每个孩子的糖果数量。我的尝试如下：

class Solution:
    def candy(self, ratings: List[int]) -> int:
        if not ratings: return 0
        n = len(ratings)
        res = [1]*n   # minimum 1 for each
        i = 1
        while i < n:
            if ratings[i-1] > ratings[i]:
                # check whether needed to add candy to current child 
                # based on right neighbor
                r = i   
                while r < n and ratings[r-1] > ratings[r]:
                    for j in range(i, r): res[j-1] += 1
                i = r
            else:
                # add candy to current child based on left neighbor
                if ratings[i-1] < ratings[i] and res[i-1] >= res[i]: res[i] = res[i-1] + 1
                i += 1
        print(res)

有人能帮我排除故障或提供一个一次性解决方案吗？

Answer 1

这是一个一次性解决方案，显示了分配给每个孩子的糖果。

def candy(ratings):
  n = len(ratings)

  # Start off giving every child one candy
  # c is array of candies
  # desc_buf is the sequence of immediately preceding rating descents
  c, desc_buf = [1]*n, []

  curr_prev_pairs = list(zip(ratings[1:], ratings))
  for i, (curr, prev) in enumerate(curr_prev_pairs, start=1):
    if curr < prev:
      # rating less than previous
      if not desc_buf:
        # start new descent sequence
        desc_buf = [i-1]
      desc_buf.append(i)
      if i != n-1:
        continue

    if curr > prev:
      # increasing rating
      c[i] = c[i-1] + 1

    if desc_buf:
      for extra, idx in enumerate(desc_buf[::-1]):
        c[idx] = max(c[idx], extra + 1)
      del desc_buf[:]

  return c

ratings = [1, 0, 2]
print(candy(ratings))    # [2, 1, 2] (5 total)

ratings = [1, 2, 2]
print(candy(ratings))    # [1, 2, 1] (4 total)