135. Candy

description

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?

题解

同样我会先给出我的想法，这道题虽然是hard，但是一点都不难（当然如果不是套路的话，我觉得我是无法优化我的代码了），看到题目后就发现有个问题，题目中没有谈到如果两个元素相等的情况，我的理解是，比如当前的值和左边的相等，那么当前的candy就需要和左边的candy相等，好吧，哗哗的写完了，结果出问题了，发现确实出在此处；题目的意思是不用管相等的情况，也就是说相等的可以赋值为1，那问题反而简单了，把之前的代码删除几行后，再submit，果然，TLE: 27/28。无语了，leetcode经常这样…
讲一下我的思路吧：对每个元素分析，如果当前元素大于前一个元素，那么当前元素的candy为前一个元素candy值再加一，如果当前元素不大于前一个元素，直接给当前元素的candy赋值1，然后判断如果前一个元素的candy等于1的话，就需要一个循环来归正前面的candy值使满足条件，循环的跳出语句就是前一个元素的rate值不大于当前元素的rate值，最后将num加起来就可以了；直接附上代码比较好：

public int candy(int[] ratings) {
    int num[]=new int[ratings.length];
    int sum=0;
    for(int i=0;i<ratings.length;i++){
        if(i==0)num[i]=1;
        else {
            if(ratings[i]>ratings[i-1])num[i]=num[i-1]+1;
            //else if(ratings[i]==ratings[i-1])num[i]=num[i-1];
            else {
                num[i]=1;
                if(ratings[i]<ratings[i-1]&&num[i-1]==1){
                    num[i-1]=2;
                    int temp=i-2;
                    while (temp>=0&&ratings[temp]>ratings[temp+1]){
                        //if(ratings[temp]==ratings[temp+1]&&num[temp]<num[temp+1])num[temp]=num[temp+1];
                        if(ratings[temp]>ratings[temp+1]&&num[temp]<=num[temp+1])num[temp]=num[temp+1]+1;
                        temp--;
                    }
                }
            }
        }
    }
    for(int i=0;i<num.length;i++){
        sum+=num[i];
    }
    return sum;
}

继续看discuss，最高票的代码我看的是满满的套路啊，又是一道左右遍历的题，感觉这些人玩上瘾了，不说什么了，直接上代码：

public int candy(int[] ratings) {
    int []sum=new int[ratings.length];
    int result=0;
    for(int i=0;i<sum.length;i++){
        sum[i]=1;
    }
    //left-right
    for(int i=1;i<sum.length;i++){
        if(ratings[i]>ratings[i-1])sum[i]=sum[i-1]+1;
    }
    //right-left
    for(int i=sum.length-1;i>0;i--){
        if(ratings[i-1]>ratings[i])sum[i-1]=Math.max(sum[i-1],sum[i]+1);
    }
    for(int i=0;i<sum.length;i++){
        result+=sum[i];
    }
    return result;
}

参考：https://discuss.leetcode.com/topic/5243/a-simple-solution