LeetCode 之135.分发糖果问题

N个数为一排，每个位置至少加1，相邻两个数评分更高的会得到更多的数，计算所有位置数之和最小。

解题思路：

相邻A与B，A在B左边，若AB，则A位置加1。

 class Solution {
 ?
 public:
   int candy(vector<int>& ratings) {
 ?    vector<int> left(ratings.size(),1);
 ?    vector<int> right(ratings.size(),1);
 ?    //左法则
 ?    for(int i=1;i<ratings.size();i++)
 ?    {
 ?      if(ratings[i]>ratings[i-1]) left[i]=left[i-1]+1;
 ?    }
 ?    int count=0;
 ?    //右法则
 ?    for(int i=ratings.size()-2;i>=0;i--)
 ?    {
 ?      if(ratings[i]>ratings[i+1]) right[i]=right[i+1]+1;
 ?      count+=max(left[i],right[i]);
 ?    }
 ?    count+=max(left[ratings.size()-1],right[ratings.size()-1]);
 ?    return count;
   }
 };

若将一排数围成一圈，依然遵循上述规则

 class Solution {
 ?
 public:
   int candy(vector& ratings) {
 ?   if(ratings.size()==0|| ratings==NULL) return 0;
     if(ratings.size()==1) return 1;
     
      vector left(ratings.size(),1);
 ?    vector right(ratings.size(),1);
 ?    //左法则
 ?    for(int i=0;i ?    {
 ?       if(i==0)
         {
             if(ratings[i]>ratings[ratings.size()-1]) //将ratings[rating.size()-1]放在放                                                     //首位左边。
               {left[i]=left[ratings.size()-1]+1;}
         }else
             {if(ratings[i]>ratings[i-1]) left[i]=left[i-1]+1;}
 ?    }
 ?    int count=0;
 ?    //右法则
 ?    for(int i=ratings.size()-1;i>=0;i--)
 ?    {
 ?      if(i==ratings.size()-1)
        {
             if(ratings[i]>ratings[0])  //将ratings[0]放在末尾右边
             {right[i]=right[0]+1;}
        }else
             {if(ratings[i]>ratings[i+1]) right[i]=right[i+1]+1;}
 ?      count+=max(left[i],right[i]);
      }
 ?    return count;
   }
 };

TRANSLATE with

Bing Webmaster Portal