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；第二遍扫描，从后向前，如果前一个比后一个大，则前一个值取当前值和右边+1的较大者。

 

public class Solution {    public int candy(int[] ratings) {        if (ratings == null || ratings.length == 0)            return 0;        int res = 0;        int len = ratings.length;        int[] num = new int[len];        num[0] = 1;        for (int i = 1; i < len; i++) {            if (ratings[i] > ratings[i - 1])                num[i] = num[i - 1] + 1;            else                num[i] = 1;        }        res += num[len - 1];        for (int i = len - 2; i >= 0; i--) {            if (ratings[i] > ratings[i + 1])                num[i] = Math.max(num[i + 1] + 1, num[i]);            res += num[i];        }        return res;    }    public static void main(String[] args) {        System.out.println(new Solution().candy(new int[] { 4, 2, 3, 4, 1 }));    }}

 

第二遍记录：

 

第三遍记录：

　　如果相邻相等的情况，貌似没有规定，就取最小的情况好了。

　　所以第一趟扫描，后续元素比前面大的时候，num增加，否则从1开始。

　　第二趟从右向左更新不满足的情况。

public class Solution {    public int candy(int[] ratings) {        int n = ratings.length;        int[] num = new int[n];        num[0]=1;        int res=0;                for(int i=1;i
     
      ratings[i-1])                num[i]=num[i-1]+1;            else                num[i]=1;                }                for(int i=n-2;i>=0;i--){            if(ratings[i]>ratings[i+1]){                num[i]=Math.max(num[i],num[i+1]+1);            }            res +=num[i];        }        res +=num[n-1];                return res;            }}
     

 

 

参考：