分发糖果

题目

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

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

每个孩子至少分配到 1 个糖果。 相邻的孩子中，评分高的孩子必须获得更多的糖果。 那么这样下来，老师至少需要准备多少颗糖果呢？

具体思路

• 从左向右遍历一遍
• 再从右向左遍历一遍

具体代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candy(ratings.size(), 1);
        int res = 0;

        // 要想好为什么不能这样写，会中间单调递增是不能传递的
        // for (int i = 0; i <= ratings.size() - 2; i++) {
        //     if (candy[i] > candy[i + 1])
        //         // candy[i]++;
        //         candy[i] = candy[i + 1] + 1;
        // }

        //为什么这样： 从左向右遍历，最左侧0，是不动的，然后调整后序
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1])
                candy[i] = candy[i - 1] + 1;
        }

        // 为什么这样：从右向左遍历，最右侧ratings.size()-1的位置是不动的
        for (int j = ratings.size() - 2; j >= 0; j--) {
            if (ratings[j] > ratings[j + 1])
                // candy[j]++;
                candy[j] = max(candy[j], candy[j + 1] + 1);
        }
        for (int i = 0; i < ratings.size(); i++)
            res += candy[i];
        return res;
    }
};

class Solution {
    public int candy(int[] ratings) {
        int total = 0;
        int[] res = new int[ratings.length];
        Arrays.fill(res, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                res[i] = res[i - 1] + 1;
            }
        }

        for (int i = ratings.length - 1; i > 0; i--) {
            if (ratings[i] < ratings[i - 1]) {
                res[i - 1] = Math.max(res[i - 1], res[i] + 1);
            }
            total += res[i];
        }
        return total + res[0];
    }
}