给每个孩子分糖果，如果这个孩子的rating比相邻的孩子高，那么他分到的糖果就要比他多，求最少需要多少糖果。
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?
Example 1:
Input: [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.Example 2:
Input: [1,2,2] Output: 4 Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions.test cases
[3,2,1,1,2,4,3,2,1,0,0] [1,0,2] [1,0,2,2,3,4,5,6,7,7,8,9,0,1,2,3,2,1,1,2,1,0] [3,2,1,1,2,3,2,2,3,4,2,2,1] [] [1,2,2,2,1,1,3,1,2,10,20,19,18,17,16,15,4,3,2,1,2,2,1,1,0,1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1,0,10] [1] [0]时间复杂度O(N)
[3,2,1,1,2,4,3,2,1,0,0]对这个用例，分法应该为：
[3,2,1,1,2,5,4,3,2,1,1]
过程为：
[1]
[2,1]
[3,2,1]
[3,2,1,1]
[3,2,1,1,2]
[3,2,1,1,2,3]
[3,2,1,1,2,3,1]
[3,2,1,1,2,3,2,1]
[3,2,1,1,2,4,3,2,1]
[3,2,1,1,2,5,4,3,2,1]
[3,2,1,1,2,5,4,3,2,1,1]
思路：维护3个变量：当前高度、前最大高度、当前台阶高度。
如果比前一个孩子分高，
如果是第一次上升，那么当前台阶高度=2，
如果不是第一次上升，那么当前台阶高度++；
结果加上当前台阶高度。
如果比前一个孩子分低，
如果不是第一次下降，那么台阶高度++；
如果是第一次下降，那么台阶高度=1；
结果加上 high < maxHigh ? high : maxHigh + 1;
如果相等，
与前面隔断。
讲不清楚，也很复杂，直接上代码
// Runtime: 2 ms, faster than 95.29% of Java online submissions for Candy. //Memory Usage: 39.7 MB, less than 16.42% of Java online submissions for Candy. public int candy(int[] ratings) { if (ratings == null || ratings.length == 0) return 0; int prev = ratings[0]; int sum = 1; int level = 1; int high = 1; int maxHigh = 1; for (int i = 1; i < ratings.length; i++) { if (ratings[i] > prev) { if (level++ == 1) high = 2; else high++; maxHigh = high; sum += level; } else if (ratings[i] < prev) { if (level == 1) { high++; } else { level = 1; high = 1; } sum += high < maxHigh ? high : maxHigh + 1; if (high == maxHigh) high++; maxHigh = Math.max(high, maxHigh); } else { level = 1; high = 1; maxHigh = 1; sum += 1; } prev = ratings[i]; } return sum; }因为有排序，时间复杂度O(NlogN(N))
贪心，思路就比较简单了，实现也简单，只是效率低一些。
永远找出分数最小的一个，如果比邻居高，那么糖果就要比高的邻居还要高，并且取最大值，分配。
根据这个思路，我很快就实现了，结果花费了20ms，花费了解1十倍的时间。
// 贪心 // Runtime: 20 ms, faster than 11.77% of Java online submissions for Candy. //Memory Usage: 45.7 MB, less than 16.42% of Java online submissions for Candy. public int candy(int[] ratings) { if (ratings == null || ratings.length == 0) return 0; Map<Integer, List<Integer>> indexes = new HashMap<>(); int[] candies = new int[ratings.length]; for (int i = 0; i < ratings.length; i++) { indexes.putIfAbsent(ratings[i], new ArrayList<>()); indexes.get(ratings[i]).add(i); } int[] sorted = Arrays.copyOf(ratings, ratings.length); Arrays.sort(sorted); int sum = 0; for (int i = 0; i < sorted.length; i++) { if (i > 0 && sorted[i] == sorted[i - 1]) continue; for (Integer j : indexes.get(sorted[i])) { if (j > 0 && ratings[j] > ratings[j - 1]) candies[j] = candies[j - 1] + 1; if (j < ratings.length - 1 && ratings[j] > ratings[j + 1]) candies[j] = Math.max(candies[j], candies[j + 1] + 1); if (candies[j] == 0) candies[j] = 1; sum += candies[j]; } } return sum; }时间复杂度O(N)
用两种方法做了之后网上看了别人的解法，发现了这种思路简单，容易实现，而且效率也高的做法。
非常赞，其实刚看到这道题的时候就想到了，但是当时就想着只遍历一次，然后在解1的路上越走越远，好在还是做出来了，但是不如解3的方法。
// Runtime: 1 ms, faster than 100.00% of Java online submissions for Candy. //Memory Usage: 39.7 MB, less than 16.42% of Java online submissions for Candy. public int candy3(int[] ratings) { int[] extraCandies = new int[ratings.length]; for (int i = 1; i < ratings.length; i++) { if (ratings[i] > ratings[i - 1]) { extraCandies[i] = extraCandies[i - 1] + 1; } } for (int i = ratings.length - 2; i >= 0; i--) { if (ratings[i + 1] < ratings[i]) extraCandies[i] = Math.max(extraCandies[i], extraCandies[i + 1] + 1); } int sum = 0; for (int extraCandy : extraCandies) { sum += extraCandy; } return sum + ratings.length; }