135. 分发糖果

135. 分发糖果

class Solution:def candy(self, ratings: List[int]) -> int:# 初始值n = ans = len(ratings)i = 0while i < n :# 从start开始，如果i>0且数组此时递增，则从前一位算起# 否则从当前i算起start = i-1 if i > 0 and ratings[i] > ratings[i-1] else i # 严格递增区间while i + 1  < n and ratings[i+1] > ratings[i]:i += 1top = i # 严格递减区间while i + 1  < n and ratings[i+1] < ratings[i]:i+=1inc = top -startdec = i-top# 递增/减段的额外糖果（等差数列求和）+峰顶的额外糖果（保证满足左右两侧）ans += ((inc-1)*inc + dec*(dec-1))//2 +max(inc,dec)i+= 1return ans