描述

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：

1. 每个孩子不管得分多少，起码分到一个糖果。
2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
   给定一个数组arr代表得分数组，请返回最少需要多少糖果。
   [要求]
   时间复杂度为, 空间复杂度为

方法一

思路

• 数组，枚举；
• 每个孩子至少会分配到一个糖果，所以创建一个一维数组，用来存储每个孩子所分配的糖果数，初始化为1，即每个孩子分配到的糖果数均为1；
• 由于题目要求在任意两个相邻的孩子之间，得分较多的孩子必须多拿一些糖果，并求出所需最少的糖果数，所以默认的情况是两个相邻孩子之间，得分较多孩子比得分较少孩子多分配一个糖果；
• 故当假设糖果是一颗一颗分配时，我们就可以模拟糖果的分配过程；譬如说对于分数数组arr{1,2,3,2,1}，首先将每个孩子分配的糖果数初始化为{1,1,1,1,1}；
• 接着比较相邻两个孩子之间的分数，判断当前的这一颗糖果应该分配给哪一个孩子，arr[1]<arr[2],所以糖果数组更新为{1,2,1,1,1}；一轮循环下来糖果数组就变成了{1,2,2,2,1}；
• 可以看见糖果数组无法满足要求，所以继续分配糖果，进行下一轮循环遍历，最终的糖果数组为{1,2,3,2,1}。
• 所以可以采取如下的糖果分配策略：
  1.首先每个孩子都初始分配一颗糖果；
  2.遍历比较每两个相邻孩子的分数，给分数高且糖果数不大于分数低的孩子一个糖果；遍历过程中设置标志位，若整个遍历过程没有修改孩子的糖果数，则糖果分配已满足题目要求；
  3.继续操作2，最多循环n次，n为孩子数；
  4.最终的糖果分配数组总和即为所需的最少的糖果数。
• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int res = 0;
        // 数组为空，返回0
        if (arr == null || arr.length == 0){
            return res;
        }
        // 存储每个孩子应该拿到的糖果数
        int[] candiesPerChild = new int[arr.length];
        // 初始化为1
        for (int i = 0;i < arr.length;++i){
            candiesPerChild[i] = 1;
        }
        // 表示第几轮糖果分配
        int index = 0;
        // 判断糖果是否分配完成
        boolean flag = true;
        int len = arr.length - 1;
        // 进行糖果分配
        while(index < arr.length){
            int i = 0;
            flag = true;
            // 每一轮分配都使得每个孩子得到的糖果数渐渐的接近所要求的分配数
            // 调整孩子所分配的糖果数量
            while(i < len){
                // 当第i个孩子分数高于第i+1个孩子，且其糖果数低于或等于第i+1个孩子时，
                // 为第i个孩子的糖果数加一
                if (arr[i] > arr[i+1] &&
                    candiesPerChild[i] <= candiesPerChild[i+1]){
                    candiesPerChild[i]++;
                    flag = false;
                }else if(arr[i] < arr[i+1] && 
                         candiesPerChild[i] >= candiesPerChild[i+1]){
                // 当第i个孩子分数低于第i+1个孩子，且其糖果数高于或等于第i+1个孩子时，
                // 为第i+1个孩子的糖果数加一
                    candiesPerChild[i+1]++;
                    flag = false;
                }
                ++i;
            }
            ++index;
            // 糖果分配完成，跳出循环
            if (flag){
                break;
            }
        }
        // 计算总的糖果数
        for (Integer num : candiesPerChild){
            res += num;
        }
        return res;
    }
  }

• 时间复杂度：,最坏的情况是孩子的分数呈升序排列，此时需要双重循环总共需要遍历n²;
• 空间复杂度：,需要长度为n的一维数组辅助计算糖果数。

方法二

思路

• 数组，贪心算法；
• 方法一的时间复杂度为,是比较大的，需要考虑降低算法的时间复杂度；
• 那么回过头来看方法一，我们可以发现每次分配糖果都只是分配一颗糖果，导致对于一个孩子要进行多次糖果分配才能达到所需要的糖果数，那么是否可以一次性分配给孩子满足要求的糖果数呢？
• 我们再反过来看糖果分配的规则，题目要求分配给两个相邻孩子中分数高的孩子较多的糖果数，即存在以及两种需要多分配糖果的情况；
• 单独考虑；即右边孩子的分数比左边孩子分数高的情况，若是得分数组中只存在这一中情况，那么只需从左往右遍历，当出现时，第i+1个孩子的糖果数为第i孩子的糖果数加一，否则的话第i+1个孩子的糖果数即为1；对于分数数组arr{1,2,3,2,1}，其糖果分配情况为{1,2,3,1,1};
• 由于忽略了；即左边孩子得分要大于右边孩子的情况，所以在需要上述步骤的基础上，从右往左遍历，找出所有左边孩子得分大于右边孩子的情况，并修正这个孩子的糖果数即可，也就是说当且第i个孩子分配的糖果数小于等于第i+1个孩子的糖果数时，第i个孩子所分配的糖果数应该修正为第i+1个孩子糖果数加一。arr{1,2,3,2,1}的糖果分配情况为{1,2,3,2,1}。
• 经过上述两次遍历，糖果分配数即可达到题目要求，所要求的最小糖果数即为数组中所有糖果数总和。
• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int res = 0;
        // 数组为空，返回0
        if (arr == null || arr.length == 0){
            return res;
        }
        // 存储每个孩子应该拿到的糖果数
        int[] candiesPerChild = new int[arr.length];
        // 初始化为1
        for (int i = 0;i < arr.length;++i){
            candiesPerChild[i] = 1;
        }
        // 从左往右遍历
        for(int i = 1;i < arr.length;++i){
            // 若右边孩子评分比左边孩子高
            if (arr[i] > arr[i-1]){
                candiesPerChild[i] = candiesPerChild[i-1]+1;
            }
        }
        // 从右往左遍历
        for (int i = arr.length - 2;i >= 0;--i){
            // 若左边孩子评分高于右边孩子评分，
            // 且左边孩子当前的糖果数是小于等于右边孩子糖果数的
            if (arr[i] > arr[i+1] && 
                candiesPerChild[i] <= candiesPerChild[i+1]){
                candiesPerChild[i] = candiesPerChild[i+1] + 1;
            }
        }
        // 计算总的糖果数
        for (Integer num : candiesPerChild){
            res += num;
        }
        return res;
    }
  }

• 时间复杂度：，两次循环遍历；
• 空间复杂度：，一维数组辅助计算。

方法三

思路

• 方法二需要的空间复杂度，而题目要求时的空间复杂度，所以还需将辅助计算的一维数组去除。
• 也就是说需要在进行糖果分配时就统计糖果分配总数，通过方法二实现是比较难的。
• 考虑糖果分配的规则，其实糖果分配的过程就类似于上下坡的过程，若孩子的分数如下表所示：
  
  其上下坡图如下：
  
• 从此图中可以看出，上坡时，分配给一个孩子的糖果数为连续上坡数加一，下坡时，分配给一个孩子的糖果数为下坡峰值减去连续下坡数，转换一下就可以看成是从右往左的上坡，也就是从右往左的连续上坡数加一；
• 峰值处需要区分从左往右的峰值peak1以及从右往左的上坡的峰值peak2，最终峰值取最大值，即max{peak1,peak2}，参考下图示例：
  
  
• 所以在计算所需最小的糖果分配总数时，可以通过计算连续上升数，连续下降数，峰值来计算最小的糖果分配总数。
• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // 糖果总数
        int res = 0;
        // 数组为空，返回0
        if (arr == null || arr.length == 0){
            return res;
        }
        // 当前连续上升数
        int up = 0;
        // 当前连续下降数
        int down = 0;
        // 峰值
        int peak = 1;
        res = 1;
        for(int i = 1;i < arr.length;++i){
            ++res;
            // 第i个孩子比第i-1个孩子的分数高
            // 连续上升个数加一
            // 当前峰的高度加一
            if (arr[i] > arr[i-1]){
                ++up;
                res += up;
                down = 0;
                peak = up + 1;
            }else if (arr[i] == arr[i-1]) {
              // 相邻两个孩子分数相同
                up = 0;
                down = 0;
                peak = 1;
            }else {
                // 第i个孩子分数低于第i+1个孩子
                // 连续下降个数加一
                up = 0;
                res += down;
                ++down;
                // 连续下降个数大于或等于当前峰值时，
                // 需要将峰值往上提一，所以总糖果数加一
                if (down >= peak){
                    res++;
                }
            }
        }
        return res;
    }
  }

• 时间复杂度：，一次循环遍历。
• 空间复杂度：,常数级空间复杂度。