[LeetCode OJ] Candy

4416 단어 LeetCode
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?
     1 class Solution {
    
     2 public:
    
     3     int candy(vector<int> &ratings) {
    
     4         vector<int> candy_number(ratings.size(), 1);
    
     5         // , , 
    
     6         for(int i=1; i<ratings.size(); ++i)
    
     7         {
    
     8            // rating , 
    
     9             if( ratings[i] > ratings[i-1])      //eg: [4 2 3 4 1], [2 1 2 3 1], 9 
    
    10                 candy_number[i] = (candy_number[i] > candy_number[i-1]+1) ? candy_number[i] : candy_number[i-1]+1;
    
    11         }
    
    12         
    
    13 
    
    14         for(int i=ratings.size()-2; i>=0; --i)   
    
    15         {
    
    16             // rating , 
    
    17             if( ratings[i] > ratings[i+1])
    
    18                 candy_number[i] = (candy_number[i] > candy_number[i+1]+1) ? candy_number[i] : candy_number[i+1]+1;
    
    19         }
    
    20 
    
    21         int total=0;
    
    22         for(int i=0; i!=ratings.size(); ++i)
    
    23             total = total + candy_number[i];
    
    24 
    
    25         return total;
    
    26     }
    
    27 };

    좋은 웹페이지 즐겨찾기