力扣135. 分发糖果#

数学解法#

• r_i：第 i 个孩子评分
• x_i：第 i 个孩子分到糖果
• L_i：从左往右遍历，满足右边 > 左边评分的最少糖果
• R_i：从右往左遍历，满足左边 > 右边评分的最少糖果
• S：糖果总数

计算公式#

x_i = \max(L_i, R_i), \quad S=\sum x_i

代码实现#

def candy(ratings):
    n = len(ratings)
    L = [1] * n  # L_i：左遍历数组
    R = [1] * n  # R_i：右遍历数组

    # 左→右算L
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            L[i] = L[i-1] + 1

    # 右→左算R
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            R[i] = R[i+1] + 1

    # x_i = max(L_i,R_i)，求和S
    total = sum(max(L[i], R[i]) for i in range(n))
    return total