LeetCode:Candy

题目地址：here

题目大意：几个小孩站一排，每个小孩有个等级值，现在给小孩发糖，发的时候要遵守2个规则：（1）每个小孩至少一颗糖（2）两个相邻的小孩中，等级大的小孩一定比等级小的小孩糖多，求发糖的数目的最小值。

本文提供两个算法，第一个是我自己做题时用的，第二个是网上看题解时看到的

算法1：该算法采用分治发，把小孩平均分左右两拨，求得两拨小孩的最小值分配方案后，还得看分界线出是否满足规则。我们用L[end]表示左边一拨小孩的右边界，R[start]表示右边一拨小孩的左边界，处理分界线出的情况分以下两种：

（1）如果L[end]等级比R[start]高，但是糖数少或相等，那么就从左边一拨小孩的右边界依次调整糖数以满足规则；

（2）如果L[end]等级比R[start]低，但是糖数多或相等，那么就从右边一拨小孩的左边界依次调整糖数以满足规则；

该算法时间复杂度为O(N*lgN)

算法1代码如下：

 1 class Solution {
 2 public:
 3     int candy(vector<int> &ratings)
 4     {
 5         // Note: The Solution object is instantiated only once and is reused by each test case.
 6         int *candyNum = new int[ratings.size()];//每个小孩的糖数目
 7         memset(candyNum,0,sizeof(int)*ratings.size());
 8         int result = candyRecursive(ratings, 0, ratings.size()-1, candyNum);
 9         delete []candyNum;
10         return result;
11     }
12 
13     int candyRecursive(vector<int> &ratings, int startloc, int endloc,
14                      int candyNum[])
15     {
16         if(startloc == endloc)
17         {
18             candyNum[startloc] = 1;
19             return 1;
20         }
21         int middle = (startloc + endloc)/2;
22         int rightCandy = candyRecursive(ratings, middle+1, endloc, candyNum);
23         int leftCandy = candyRecursive(ratings, startloc, middle, candyNum);
24         if(ratings[middle+1] > ratings[middle])
25         {
26             int tmp = candyNum[middle+1] - candyNum[middle];
27             if(tmp <= 0)
28             {
29                 tmp *= -1;
30                 candyNum[middle+1] += (tmp+1);
31                 rightCandy += (tmp+1);
32                 for(int i = middle+2; i <= endloc; i++)
33                 {
34                     if(ratings[i] > ratings[i-1] && candyNum[i] <= candyNum[i-1])
35                     {
36                         int foo = candyNum[i-1] - candyNum[i] + 1;
37                         candyNum[i] += foo;
38                         rightCandy += foo;
39                     }
40                     else break;
41                 }
42             }
43         }
44         else if(ratings[middle+1] < ratings[middle])
45         {
46             int tmp = candyNum[middle+1] - candyNum[middle];
47             if(tmp >= 0)
48             {
49                 candyNum[middle] += (tmp+1);
50                 leftCandy += (tmp+1);
51                 for(int i = middle-1; i >= startloc; i--)
52                 {
53                     if(ratings[i] > ratings[i+1] && candyNum[i] <= candyNum[i+1])
54                     {
55                         int foo = (candyNum[i+1] - candyNum[i] + 1);
56                         candyNum[i] += foo;
57                         leftCandy += foo;
58                     }
59                     else break;
60                 }
61             }
62         }
63         return leftCandy + rightCandy;
64     }
65 };

算法2：初始化所有小孩糖数目为1，从前往后扫描，如果第i个小孩等级比第i-1个高，那么i的糖数目等于i-1的糖数目+1；从后往前扫描，如果第i个的小孩的等级比i+1个小孩高,但是糖的数目却小或者相等，那么i的糖数目等于i+1的糖数目+1。

该算法时间复杂度为O(N)

算法2代码如下：

 1 class Solution {
 2 public:
 3     int candy(vector<int> &ratings)
 4     {
 5         // Note: The Solution object is instantiated only once and is reused by each test case.
 6         int *candyNum = new int[ratings.size()];//每个小孩的糖数目
 7         for(int i = 0; i < ratings.size(); i++)
 8             candyNum[i] = 1;
 9         for(int i = 1; i < ratings.size(); i++)
10             if(ratings[i] > ratings[i-1])
11                 candyNum[i] = candyNum[i-1] + 1;
12         for(int i = ratings.size()-2; i>=0; i--)
13             if(ratings[i] > ratings[i+1] && candyNum[i] <= candyNum[i+1])
14                 candyNum[i] = candyNum[i+1] + 1;
15         int result = 0;
16         for(int i = 0; i < ratings.size(); i++)
17             result += candyNum[i];
18         delete []candyNum;
19         return result;
20     }
21 };