Leetcode#135 Candy

遍历所有小孩的分数

1. 若小孩的分数递增，分给小孩的糖果依次+1
2. 若小孩的分数递减，分给小孩的糖果依次-1
3. 若小孩的分数相等，分给小孩的糖果设为1

当递减序列结束时，如果少分了糖果，就补上，如果多分了糖果，就减掉

究竟补多少或减多少，这很容易计算，不啰嗦了。

时间复杂度：O(n)

代码：

 1 int candy(vector<int> &ratings) {
 2   int n = ratings.size();
 3   int sum = 1;
 4   int len = 0;
 5   int prev = 1;
 6 
 7   for (int i = 1; i < n; i++) {
 8     if (ratings[i] == ratings[i - 1]) {
 9       prev = 1;
10       len = 0;
11       sum += prev;
12     }
13     else if (ratings[i] > ratings[i - 1]) {
14       prev++;
15       len = 0;
16       sum += prev;
17     }
18     else if (ratings[i] < ratings[i - 1]) {
19       prev--;
20       len++;
21       sum += prev;
22       if (i == n - 1 || ratings[i] <= ratings[i + 1]) {
23         sum += prev < 1 ? (1 - prev) * (len + 1) : (1 - prev) * len;
24         prev = 1;
25       }
26     }
27   }
28 
29   return sum;
30 }