[leetcode]Candy

Candy

 

AC Rate: 1460/9941

 

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

 

本题有一点需要注意的是，题目只要求相邻小朋友rating大的，candies分得多。

对于相邻的小朋友ratings相同可以分得个数不一样的糖果。

也就是 1 2 3 3 3 3 4 5 糖果数

 对应为1 2 3 1 1 1 2 3是合理的。中间的两个3 3 随便取值，但是min的话肯定是取1啦

 

定义c[i]表示小朋友i可以分得的最少糖果数

因为上述ratings相等的情况合理，那么可以不考虑ratings相等的情况，

可以把这个数组其他部分分成若干严格单调区间[升，降随意组合]，观察可知：

1 对于上拐点 c[i] =max（升区间长度，降区间长度）；

2 对于下拐点c[i]肯定等于1 然后随着区间，逐渐递增；

 

然后我就陷入了找升降区间的思路中不可自拔-。-

然后看了大牛们代码发现，可以分两遍扫；

1. 第一遍扫严格单调增区间，c[i] = c[i-1]+1;

2. 第二遍扫严格单调减区间， Math.max(c[i],c[i+1]+1);其中c[i]是第一遍扫单增区间的赋值，

c[i+1]+1是本次扫单减区间的赋值；似乎只用考虑上拐点就可以了，

但是拐点的判断有点麻烦，所以每个都考虑下好了-。-

同时在第二遍扫的过程中就可以把min求出来。

 

代码：

 

 public int candy(int[] ratings) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(ratings == null||ratings.length == 0) return 0;
        int len = ratings.length;
        int c[] = new int[len];
        Arrays.fill(c,1);
      
        for(int i = 1;i<=len-1;i++){
            if(ratings[i]>ratings[i-1])//单增区间
                c[i] = c[i-1]+1;
        } 
        //c[len-1]的值不会改变了，因为len-1是：
        //1. 单增区间的尾部，后面没有值了，不是上拐点
        //2. 单减区间的尾部，肯定是初始值1
        //3. 某一重复值，取初始值1
        int min = c[len-1];
        for(int i = len-2;i>=0;i--){//单减区间
            if(ratings[i+1]<ratings[i]){
                c[i] = Math.max(c[i],c[i+1]+1);
            }
            min = min+c[i];
        }
        return min;
    }

 

ps 这种两种单调的情况可以扫两遍啊亲，我记得买卖股票那题也似这种方式扫两遍啊，

不长记性!!我回去在把那题做一遍。。