135. 分发糖果 (opens new window)

1.中心扩散+边界判断

思路：第一轮遍历找到所有的波谷，然后从波谷向两侧扩散计算每个节点的糖果数；第二轮根据左右两个节点的最大值计算所有波峰的值。

以ratings=[1，6，6，6，3，7，10，9，5，2，2，2，7，4，1，3，6]为例，下图每个节点的值表示对应分发的糖果数，相对高度对应每个孩子的评分，评分越高位置越往上。红色方框代表搜索出的波谷，蓝色方框代表波峰。如图所示：

扩散算法中需要多种情况的边界，包括水平的情况和递增：

• 相比前一个节点如果当前处于递增的趋势，则直接更新。
• 如果当前节点与前一个节点相等，则还需要再往下看一个节点决定当前节点的更新情况，分为两种情况：
  • 下一个节点如果处于“非递减”趋势，则置为1
  • 下一个节点如果是递减，如上面紫色节点2，则停止更新。

class Solution {
    int[] res;
    public int candy(int[] ratings) {
        if(ratings.length==1) return 1;
        res=new int[ratings.length];
        int ans=0;
        //扩散
        for(int i=0;i<ratings.length;i++){
            if(res[i]==0){
                if(i==0&&ratings[i]<=ratings[i+1]){
                    res[i]=1;
                    diff(ratings,i);
                }
                if(i==ratings.length-1&&ratings[i]<=ratings[i-1]){
                    res[i]=1;
                    diff(ratings,i);
                }
                if(i>0&&i<ratings.length-1){
                    if(ratings[i-1]>=ratings[i]&&ratings[i]<=ratings[i+1]){
                        res[i]=1;
                        diff(ratings,i);
                    }
                }
            }
        }
        //填补计算顶点值
        for(int i=0;i<ratings.length;i++){
            if(res[i]==0){
                int left=i-1>=0?res[i-1]:0;
                int right=i+1<ratings.length?res[i+1]:0;
                res[i]=Math.max(left,right)+1;
            }
            ans+=res[i];
        }
        return ans;

    }
    public void diff(int[] ratings,int index){
        //向右边扩散
        int right=index+1;
        while(right<ratings.length){
            if(ratings[right]>ratings[right-1]){
                if(right==ratings.length-1) res[right]=res[right-1]+1;
                else{
                    if(ratings[right]>ratings[right+1]) break;
                    else res[right]=res[right-1]+1;
                }
            }
            else if(ratings[right]==ratings[right-1]){
                if(right+1<ratings.length&&ratings[right]>ratings[right+1])break;
                else  res[right]=1;
            }
            else break;
            right++;
        }
        //向左扩散
        int left=index-1;
        while(left>=0){
            if(ratings[left]>ratings[left+1]){
                if(left==0) res[left]=res[left+1]+1;
                else {
                    if(ratings[left]>ratings[left-1])break;
                    else res[left]=res[left+1]+1;
                }
            }
            else if(ratings[left]==ratings[left+1]){
                if(left-1>=0&&ratings[left]>ratings[left-1])break;
                else  res[left]=1;
            }
            else break;
            left--;
        }
    }
}