1
2
3

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

1
2
3
4

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 两次遍历
    /// 1.规则2等价于:
    ///    a. 自左至右遍历, 如果ratings[i] > ratings[i-1], 则当前糖果在前一人基础上+1;
    ///    b. 自右至左遍历, 如果ratings[i] > ratings[i+1], 则当前糖果在后一人基础上+1;
    ///   遍历玩后,选择每个人中糖果多的那个作为最后的分发的糖果
    pub fn candy(ratings: Vec<i32>) -> i32 {
        let mut candy = 1;
        let mut left = vec![1; ratings.len()];
        for i in 1..ratings.len() {
            if ratings[i] > ratings[i - 1] {
                candy += 1;
            } else {
                candy = 1;
            }
            left[i] = candy;
        }
        let mut total = 0;
        for i in (0..ratings.len()).rev() {
            if i < ratings.len() - 1 && ratings[i] > ratings[i + 1] {
                candy += 1;
            } else {
                candy = 1;
            }

            total += candy.max(left[i]);
        }

        total
    }
}
// @lc code=end