LeetCode--135. 分发糖果

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。

• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

---

有点意思，没写出来。

两次遍历

由于每个孩子至少分配一个糖果，并且相邻两个孩子，评分更高的孩子要多得到糖果，所以既然需要考虑相邻的孩子，我们可以将其拆分为左边和右边两种情况，然后取最大值。

首先我们从左向右遍历的时候，我们在给这个孩子分配糖果的时候，需要考虑到前一个孩子和评分以及分配了多少糖果，如果前一个评分更高，那么直接给这个孩子分配1个糖果就行，如果这个孩子评分更高，那么这个孩子分配的糖果是前一个孩子分配的糖果的数量+1，那么此时我们便能得到如果只考虑一边的孩子的情况，随后，我们从右向左遍历，也是一样的做法，然后取一个交集，就能得到既能满足左规则，又能满足右规则的最大值。

func candy(ratings []int) int {
    n := len(ratings)
    ans := 0
    left := make([]int, n)
    for i, r := range ratings {
        if i > 0 && r > ratings[i - 1] {
            left[i] = left[i - 1] + 1
        } else {
            left[i] = 1
        }
    }
    right := 0
    for i := n - 1; i >= 0; i -- { 
        if i < n - 1 && ratings[i] > ratings[i + 1] {
            right ++
        } else {
            right = 1
        }
        ans += max(left[i], right)
    }
    return ans
}

感觉不太好理解，看看下一个方法。

巧妙的，更易理解的解法

虽然我一开始确实是想的类似这样的解法，但是还是有部分要素没考虑进去，就没写出来。

首先，每个孩子必须要分配一个糖果，而相邻的孩子，评分更好的会得到更多的糖果，如果此时这个孩子是在评分严格单调递增的序列中，而在这个序列的第一个孩子的糖果一定为1，所以相当于这个孩子分到的糖果，就是当时单调递增序列的长度，值得注意的是，这个序列并不包含等于的情况，如果出现等于，序列的长度就会变成1。

而在序列单调递减的时候，我们的最后一个元素一定应该为1，所以，这个时候我们整体的序列可以倒过来看，将单调递减的序列，按照单调递增的形式加起来，这样就得到了我们的真实的糖果数量，而不需要在遍历单调递减的序列的最开始就为第一个孩子赋予糖果。

func candy(ratings []int) int {
    n := len(ratings)
    ans, inc, dec, pre := 1, 1, 0, 1
    for i := 1; i < n; i ++ {
        if ratings[i] >= ratings[i - 1] {
            dec = 0
            if ratings[i] == ratings[i - 1] {
                pre = 1
            } else {
                pre ++
            }
            ans += pre
            inc = pre
        } else {
            dec ++
            if dec == inc {
                dec ++
            }
            ans += dec
            pre = 1
        }
    } 
    return ans
}