LeetCode问题135Candy one-pass解决方案:计算每个孩子得到的糖果数量

Question

problem (https://leetcode.com/problems/candy/description/)语句如下：

有N个孩子在排队。每个孩子都被分配了一个评分值。你要给这些孩子糖果，但要遵守以下要求：

(1)每个孩子必须至少有一颗糖果。

(2)评分越高的孩子得到的糖果越多。

(3)你必须给的最低糖果是多少？

例如:输入: 1,0,2，输出: 5；输入: 1,2,2，输出:4

在问题讨论中，提出了一次通过的解决方案：

https://leetcode.com/problems/candy/discuss/42770/One-pass-constant-space-Java-solution

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

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)