题解 | #分糖果问题#

解题思路就是把数组切割成 N 个倒叙数组。然后再处理，具体看下面代码注释

/**
 * pick candy
 * @param arr int整型一维数组 the array
 * @return int整型
 */
function candy( arr ) {
    // write code here
    var num = 0, //最少分的糖果
        disList=[], //存每个得分分到的糖果
        arrb = []; //把arr 得分分割成N 个倒叙排列的数组，存到arrb;
    for(i=0;i<arr.length;i++){
        if(i== 0){
            arrb.push([]);
        }
        if(arr[i] > arr[i+1]){
            arrb[arrb.length-1].push(arr[i]);
        }else {
            arrb[arrb.length-1].push(arr[i]);
            arrb[arrb.length] = [];
        }
    };
    for(i=0;i<arrb.length; i++){
        let dis = arrb[i].length; //每一组倒序数组每次要分的糖果最高数量
      //由于切割数组时候有些倒叙数组只有一个值，所以需要判断前当前最高分的数量是否小于前一个数组的最低数量
        if(disList[disList.length - 1] && dis <= disList[disList.length - 1] ){
            if(arrb[i][0] > arrb[i-1][arrb[i-1].length -1] ) {
                dis = disList[disList.length - 1] + 1;
            }
        }
        //开始分糖果，当分糖果第一个分到 dis 数量的也就是最多的糖果。分完第一个第二个分的数量不能是dis-1 需要变成当前倒叙列的长度 -1;这样处理分到最后一个就会只分1个。得到这一组倒叙的分的最少苹果的
        for(k=0;k<arrb[i].length;k++){
            if(k == 0){
                num += dis;
                disList.push(dis);
                dis = arrb[i].length - 1; 
            }else {
                num += dis;
                disList.push(dis);
                dis -= 1;
            }
            
        } 
    }
    return num;
}
module.exports = {
    candy : candy
};