Candy 

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根，从左往右扫，如果发现当前的rating小于左边的rating，给的糖比左边的多1。

第二轮从倒数第二个小盆与开始，从右往左扫，如果发现当前的rating小于右边的rating，并且糖也少，给的糖比左边的多1。

1 /** 2  * @param {number[]} ratings 3  * @return {number} 4  */ 5 var candy = function(ratings) { 6     var i, result; rates = []; 7     rates[0] = 1; 8     for(i = 1; i < ratings.length; i++){ 9         if(ratings[i] > ratings[i - 1]){10             rates[i] = rates[i - 1] + 1;11         }else{12             rates[i] = 1;13         }14     }15     result = rates[ratings.length - 1];16     for(i = ratings.length - 2; i >= 0; i--){17         if(ratings[i] > ratings[i + 1] && rates[i] <= rates[i + 1]){18             rates[i] = rates[i + 1] + 1;19         }20         result += rates[i];21     }22     return result;23 };

 

一开始想了一个解法，有点费劲。

第一轮遍历，如果这个小盆与比左右的rating都要小，他肯定是1，把index加入到queue中。

然后就开始递归，有点像bfs。

这样递归的话，保证大的rating一定后做，先处理的是较小的rating。

递归的时候分两种情况：

1. 当前ratings小于左边且大于右边 或者 当前ratings小于右边且大于左边。

因为大的一定后做，所以可以确定当前点的糖数，等于max(左边糖，右边糖) + 1，注意这里如果还没有给过糖，默认值是0，较大的一边是0。

2. 如果两边都给过糖了，并且当前ratings大于左边且大于右边，当前节点的糖数也是等于max(左边糖，右边糖) + 1。

这一轮给完糖后，把左边右边和当前的没有发过糖的节点都塞进queue中。

虽然比较复杂，时间复杂度仍然是O(n)。

但是交上去之后12000的那组数据堆栈溢出。

唉，本地测试10几毫秒妥妥的，leetcode的JS小堆栈居然爆了，是在下输了。

1 /** 2  * @param {number[]} ratings 3  * @return {number} 4  */ 5 var candyMLE = function(ratings) { 6     var queue = [], result = 0, rates = []; 7     for(var i = 0; i < ratings.length; i++){ 8         if(ratings[i - 1] && ratings[i - 1] < ratings[i]){ 9             continue;10         }11         if(ratings[i + 1] && ratings[i + 1] < ratings[i]){12             continue;13         }14         queue.push(i);15         result++;16         rates[i] = 1;17     }18     bfs(queue);19     return result;20 21     function bfs(queue){22         var len = queue.length;23         if(queue.length !== 0){24             while(len--){25                 var top = queue.shift();26                 if(!rates[top]){27                     giveCandy(queue, top);28                 }29                 if(!rates[top - 1] && ratings[top - 1] && queue.indexOf(top - 1) === -1){30                     queue.push(top - 1);31                 }32                 if(!rates[top + 1] && ratings[top + 1] && queue.indexOf(top + 1) === -1){33                     queue.push(top + 1);34                 }   35                 if(!rates[top] && queue.indexOf(top) === -1){36                     queue.push(top);37                 }     38             }39             bfs(queue);    40         }41     }42     function giveCandy(queue, i){43         if(ratings[i]){            44             var leftValue = ratings[i - 1] || 0;45             var leftRate = rates[i - 1] || 0;46             var rightValue = ratings[i + 1] || 0;47             var rightRate = rates[i + 1] || 0;48             if(ratings[i] > leftValue && ratings[i] < rightValue || 49                 ratings[i] < leftValue && ratings[i] > rightValue ||50                 ratings[i] >= leftValue && ratings[i] >= rightValue && (leftRate !== 0 || !ratings[i - 1])){51                 rates[i] = Math.max(leftRate, rightRate) + 1;52                 result += rates[i];53             }54         }55     }56 };