A simple solution


  • 210
    1
      int candy(vector<int> &ratings)
     {
    	 int size=ratings.size();
    	 if(size<=1)
    		 return size;
    	 vector<int> num(size,1);
    	 for (int i = 1; i < size; i++)
    	 {
    		 if(ratings[i]>ratings[i-1])
    			 num[i]=num[i-1]+1;
    	 }
    	 for (int i= size-1; i>0 ; i--)
    	 {
    		 if(ratings[i-1]>ratings[i])
    			 num[i-1]=max(num[i]+1,num[i-1]);
    	 }
    	 int result=0;
    	 for (int i = 0; i < size; i++)
    	 {
    		 result+=num[i];
    		// cout<<num[i]<<" ";
    	 }
    	 return result;
     }

  • -29
    U

    Good solution, same as mine in Java.

    —————————————————————

    The upper was my first comment, and gained many -1.
    So I post my java code as the second comment.
    This is my third comment, to explain .


    As some guys want to see my code, see below please.

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

  • 0
    N

    Why In second scan we are traverse from the end, Why not starting from start.


  • 5
    W

    It's due to the computation dependency. In the second scan, num[i-1]=max(num[i]+1,num[i-1]). In other words, num[i-1] depends on num[i]. So num[i] must be computed before num[i-1].


  • 0
    Z

    really easy to understand. good solution.


  • 0
    A

    very simple, I understand, thanks for sharing your code~


  • 0

    Incredibly simple code! I am really interested in your thouhgt process of how to come up with such a nice solution :-)


  • 0
    D

    Any one can prove this solution is correct?


  • -1

    U can U show your JAVA code, no can no bb.


  • 0

    Many thanks for your solution.
    if input array is 1,3,3,3,2, candy is 1,2,1,2,1 rather than '1,2,2,2,1'.


  • 1
    L

    good! I was thinking how to deal with equal rates. when one children's rate equal with both neighbors, give him one candy would be enough.


  • 0
    V

    23333333333333


  • 0
    S

    I don't know what you said before so that got so many downs..... But the code is really nice. help you to cancel a -1...


  • -1

    Yes, the idea and code is quite good and easy to understand. I will help you cancel a -1 and add a +1.


  • 0
    J

    Sharing good solution should be inspired. So UP + 1.


  • 0
    J

    Great idea !


  • 0

    Really interested in what you said in your post. Why you got so many votes down?


  • -2
    Z

    I don't know what happened, but I think there must be some reason why so many people vote down on you, so I follow them -1


  • 1

    Let's start taking guess of what he could have posted.
    "Here's my JAVA code" .. and then he forgot to post the code


  • 0
    L

    Exciting solution and I helped you vote it up...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.