/*
1. 相邻的孩子中，评分高的孩子必须获得更多的糖果 -> 
    左相邻且分高的孩子糖果 > 当前孩子, 否则补足并+1
    右相邻且分高的孩子糖果 > 当前孩子, 否则补足并+1
2. 左右扫描两遍求和即可
*/


class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] scores = new int[n];
        for (int i = 1 ; i < n ; i ++) {
            if (ratings[i] > ratings[i-1] && scores[i] <= scores[i-1]){
                scores[i] +=  (scores[i-1] - scores[i] + 1);
            }
        }
        for (int i = n-2 ; i >= 0; i--){
            if (ratings[i] > ratings[i+1] && scores[i] <= scores[i+1]){
                scores[i] += (scores[i+1] - scores[i] + 1);
            }
        }
        return Arrays.stream(scores).sum() + n;
    }
}


/* 开始想的错误做法, 无法使相等情况左右都满足
1. 一个乱序数组可以划分为多段递增或递减的子数组, 即是"w"型或"M"型, 相等情况可以融合到任意一个中
2. 从左到右扫描, 分为两种情况:
    单调递增序列每个比前一个多1, 
    相等或递减序列每个比前一个少1,
    由于需求为使用最少, 所以极小值点设定为1, 如果不为1,调整整个数组 -> 差分调整

3. 得出每个孩子的糖果后求和
*/