[leetcode] Candy

首先想到的solution是把array排列一下... 然后从小到大 去sum candy总数。每当遇到一个新的数 就把single round candy 增加1

..发现理解题意错了... 原来rating高的时候只要比neighbor 高 就可以了
。。还有一个很独特的case 题目好像没说清楚..就是当两个neighbor rating一样高的时候 后者只能拿一颗糖


思路：
candy[i] = candy[i-1]+1 when ratings[i] > ratings[i-1]
                 1                     when ratings[i] == ratings[i-1]
                candy[i-1]-1 when ratings[i] < ratings[i-1] (adjustment needs to be made)


首先向左扫描一次... 把递增的都算好。。递减的 就直接assign 1
然后再向右扫描一次 把错的值adjust 回来

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

public class Solution { public int candy(int[] ratings) { if (ratings == null || ratings.length == 0){ return 0; } int localCache[] = new int[ratings.length]; localCache[0] = 1; for (int i = 1; i < ratings.length; i++){ if (ratings[i] > ratings[i-1]){ localCache[i] = localCache[i-1]+1; }else{ localCache[i] = 1; } } int sum = localCache[localCache.length-1]; for (int i = ratings.length-2; i >= 0; i--){ if (ratings[i] > ratings[i+1] && localCache[i] <= localCache[i+1]){ localCache[i] = localCache[i+1]+1; } sum += localCache[i]; } return sum; } }