题目

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

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

每个孩子至少分配到 1 个糖果。
相邻两个孩子中，评分更高的那个会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

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

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

题解

假设第 i 个孩子是一个“峰顶”，即他的评分比左边高，也比右边高（ratings[i-1] < ratings[i] > ratings[i+1]）。
满足左规则的要求：根据从左向右的遍历，为了满足他比左边孩子分多，他至少需要 left[i] 个糖果。例如：左边是一路升上来的，1 < 2 < 3 < 5 (当前)。为了比左边大，他根据左坡度累积，至少要拿 4 个。
满足右规则的要求：根据从右向左的遍历，为了满足他比右边孩子分多，他至少需要 right[i] 个糖果。例如：右边是一路降下去的，5 (当前) > 4 > 3 > 2 > 1。为了比右边大，他根据右坡度累积，至少要拿 5 个。
同时满足的要求：我们要找一个数 x，使得 x >= left[i] 且 x >= right[i]。为了使总糖果数最少，我们取这两个限制条件的最大值即可。如果取 min（比如取 4）： 虽然满足了比左边大，但不够分给右边的坡度（右边坡度要求至少 5 个才能压住右边的邻居），这违反了右规则。如果取 max（比如取 5）：满足右规则（正好 5 个）。满足左规则（5 个肯定大于左边邻居要求的 4 个，毕竟 $5 > 4$）。

总结一句话：left[i] 代表“为了压住左边，我至少要多少”，right[i] 代表“为了压住右边，我至少要多少”。只有取最大值，才能同时撑起左边和右边的“坡度”，并且保持数值最小。

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];

        // 1. 初始化，每个人至少分 1 个
        // 实际上我们可以直接在遍历中赋值

        // --- 第一次遍历：从左向右 ---
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }

        // --- 第二次遍历：从右向左 ---
        // 我们不需要显式建立 right 数组，可以直接用一个变量维护，或者直接在 left 数组上取 max
        // 为了清晰，这里直接修改 left 数组作为最终结果

        int right = 0; // 用于记录当前位置满足右规则所需的糖果数
        int ret = 0;   // 总糖果数

        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && ratings[i] > ratings[i + 1]) {
                right = right + 1;
            } else {
                right = 1;
            }

            // 关键点：取 max
            // left[i] 目前存的是满足左规则的值
            // right 存的是满足右规则的值
            // 取 max 后，left[i] 就变成了同时满足左右规则的值
            ret += Math.max(left[i], right);
        }

        return ret;
    }
}