candy leetcode

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?

与trapping rain water相同, 初始化所有都为1

从左往右遍历找到相对于左边所需要的最小数量  这一次保证相邻儿童比左边的rating高的拿得多

再从右往左遍历找到相对于右边最小数量, 这一次遍历可以保证相邻的儿童比右边rating高的拿得多, 不会影响左边的 因为左边相邻的也可以确保比他的右边rating高的拿得多

最终数量为这两个数量中最大的
时间O(n) 空间 O(n)

public class Solution {
    public int candy(int[] ratings) {
       if (ratings.length == 0 || ratings == null) {
           return 0;
       }
       int len = ratings.length;
       int[] left = new int[len];
       int[] right = new int[len];
       left[0] = 1;
       for (int i = 1; i < len; i++) {
           if (ratings[i] > ratings[i-1]) {
               left[i] = left[i-1] +1;
           } else {
               left[i] = 1;
           }
       }
       right[len - 1] = left[len - 1];
       for (int j = len - 2; j >= 0; j--) {
           if (ratings[j] > ratings[j + 1]) {
               right[j] = right[j +1] +1;
           } else {
               right[j] = 1;
           }
       }
       int res = 0;
       for (int i = 0; i < len; i++) {
           res += Math.max(left[i], right[i]);
       }
       return res;
    }
}