题目描述（困难难度）

135. Candy - 图1

给 N 个小朋友分糖，每个人至少有一颗糖。并且有一个 rating 数组，如果小朋友的 rating比它旁边小朋友的 rating 大（不包括等于），那么他必须要比对应小朋友的糖多。问至少需要分配多少颗糖。

用 - 表示糖，举几个例子。

  1. 1 0 2
  2. - - -
  3. -   -
  4. 总共就需要 5 颗糖。
  6. 1 2 2
  7. - - -
  8.   -
  9. 总共就需要 4 颗糖。

解法一

根据题目，首先每个小朋友会至少有一个糖。

如果当前小朋友的 rating 比后一个小朋友的小，那么后一个小朋友的糖肯定是当前小朋友的糖加 1。

比如 ration = [ 5, 6, 7] ，那么三个小朋友的糖就依次是 1 2 3。

如果当前小朋友的 rating 比后一个小朋友的大，那么理论上当前小朋友的糖要比后一个的小朋友的糖多，但此时后一个小朋友的糖还没有确定，怎么办呢？

参考 32题 的解法五，利用正着遍历，再倒着遍历的思想。

首先我们正着遍历一次，只考虑当前小朋友的 rating 比后一个小朋友的小的情况。

接着再倒着遍历依次，继续考虑当前小朋友的 rating 比后一个小朋友的小的情况。因为之前已经更新过一次糖果了，此时后一个小朋友的糖如果已经比当前小朋友的糖多了，就不需要进行更新了。

举个例子

  1. 初始化每人一个糖
  2. 1 2 3 2 1 4
  3. - - - - - -.
  5. 只考虑当前小朋友的 rating 比后一个小朋友的小的情况,后一个小朋友的糖是当前小朋友的糖加 1。
  6. 1 < 2
  7. 1 2 3 2 1 4
  8. - - - - - -
  9.   -   
  11. 2 < 3
  12. 1 2 3 2 1 4
  13. - - - - - -
  14.   - -
  15.     -
  17. 3 > 2 不考虑
  19. 2 > 1 不考虑
  21. 1 < 4
  22. 1 2 3 2 1 4
  23. - - - - - -
  24.   - -     -
  25.     -
  27. 倒过来重新进行
  28. 继续考虑当前小朋友的 rating 比后一个小朋友的小的情况。此时后一个小朋友的糖如果已经比当前小朋友的糖多了，就不需要进行更新。
  29. 4 1 2 3 2 1
  30. - - - - - -
  31. -     - -
  32.       -
  34. 4 > 1 不考虑
  36. 1 < 2
  37. 4 1 2 3 2 1
  38. - - - - - -
  39. -   - - -
  40.       -    
  42. 2 < 3，3 的糖果已经比 2 的多了，不需要考虑
  44. 3 > 2，不考虑
  46. 2 > 1，不考虑
  48. 所以最终的糖的数量就是上边的 - 的和。

代码的话，我们用一个 candies 数组保存当前的分配情况。

  1. public int candy(int[] ratings) {
  2.     int n = ratings.length;
  3.     int[] candies = new int[n];
  4.     //每人发一个糖
  5.     for (int i = 0; i < n; i++) {
  6.         candies[i] = 1;
  7.     }
  8.     //正着进行
  9.     for (int i = 0; i < n - 1; i++) {
  10.         //当前小朋友的 rating 比后一个小朋友的小,后一个小朋友的糖是当前小朋友的糖加 1。
  11.         if (ratings[i] < ratings[i + 1]) {
  12.             candies[i + 1] = candies[i] + 1;
  13.         }
  14.     }
  15.     //倒着进行
  16.     //下标顺序就变成了 i i-1 i-2 i-3 ... 0
  17.     //当前就是第 i 个，后一个就是第 i - 1 个
  18.     for (int i = n - 1; i > 0; i--) {
  19.         //当前小朋友的 rating 比后一个小朋友的小
  20.         if (ratings[i] < ratings[i - 1]) {
  21.             //后一个小朋友的糖果树没有前一个的多，就更新后一个等于前一个加 1
  22.             if (candies[i - 1] <= candies[i]) {
  23.                 candies[i - 1] = candies[i] + 1;
  24.             }
  26.         }
  27.     }
  28.     //计算糖果总和
  29.     int sum = 0;
  30.     for (int i = 0; i < n; i++) {
  31.         sum += candies[i];
  32.     }
  33.     return sum;
  34. }

时间复杂度：O（n）。

空间复杂度：O（n）。

解法二

参考 这里。

解法一中，考虑到

如果当前小朋友的 rating 比后一个小朋友的大，那么理论上当前小朋友的糖要比后一个的小朋友的糖多，但此时后一个小朋友的糖还没有确定，怎么办呢？

之前采用了倒着遍历一次的方式进行了解决，这里再考虑另外一种解法。

考虑下边的情况。

135. Candy - 图2

对于第 2 个 rating 4，它比后一个 rating 要大，所以要取决于再后边的 rating，一直走到 2，也就是山底，此时对应的糖果数是 1，然后往后走，走回山顶，糖果数一次加 1，也就是到 rating 4 时，糖果数就是 3 了。

再一般化，山顶的糖果数就等于从左边的山底或右边的山底依次加 1 。

所以我们的算法只需要记录山顶，然后再记录下坡的高度，下坡的高度刚好是一个等差序列可以直接用公式求和。而山顶的糖果数，取决于左边山底到山顶和右边山底到山顶的哪个高度大。

而产生山底可以有两种情况，一种是 rating 产生了增加，如上图。还有一种就是 rating 不再降低，而是持平。

知道了上边的想法，基本上就可以写代码了，每个人写出来的应该都不一样，在 discuss 区也看到了很多不同的写法，下边说一下我的思路。

抽象出四种情况，这里的高度不是 rating 进行相减，而是从山底的 rating 到山顶的 rating 经过的次数。

  1. 左边山底到山顶的高度大，并且右边山底后继续增加。

    135. Candy - 图3

  2. 左边山底到山顶的高度大，并且右边山底是平坡。

    135. Candy - 图4

  3. 右边山底到山顶的高度大，并且右边山底后继续增加。

    135. Candy - 图5

  4. 右边山底到山顶的高度大，并且右边山底是平坡。

    135. Candy - 图6

有了这四种情况就可以写代码了。

我们用 total 变量记录糖果总和， pre 变量记录前一个小朋友的糖果数。如果当前的 rating 比前一个的 rating 大，那么说明在走上坡，可以把前一个小朋友的糖果数加到 total 中，并且更新 pre 为当前小朋友的糖果数。

如果当前的 rating 比前一个的 rating 小，说明开始走下坡，用 down 变量记录连续多少次下降，此时的 pre 记录的就是从左边山底到山底的高度。当出现平坡或上坡的时候，将所有的下坡的糖果数利用等差公式计算。此外根据 pre 和 down 决定山顶的糖果数。

根据当前是上坡还是平坡，来更新 pre。

大框架就是上边的想法了，还有一些边界需要考虑一下，看一下代码。

  1. public int candy(int[] ratings) {
  2.     int n = ratings.length;
  3.     int total = 0;
  4.     int down = 0;
  5.     int pre = 1;
  6.     for (int i = 1; i < n; i++) {
  7.         //当前是在上坡或者平坡
  8.         if (ratings[i] >= ratings[i - 1]) {
  9.             //之前出现过了下坡
  10.             if (down > 0) {
  11.                 //山顶的糖果数大于下降的高度，对应情况 1
  12.                 //将下降的糖果数利用等差公式计算，单独加上山顶
  13.                 if (pre > down) {
  14.                     total += count(down);
  15.                     total += pre;
  16.                 //山顶的糖果数小于下降的高度，对应情况 3，
  17.                 //将山顶也按照等差公式直接计算进去累加
  18.                 } else {
  19.                     total += count(down + 1);
  20.                 }
  22.                 //当前是上坡，对应情况 1 或者 3
  23.                 //更新 pre 等于 2
  24.                 if (ratings[i] > ratings[i - 1]) {
  25.                     pre = 2;
  27.                 //当前是平坡，对应情况 2 或者 4
  28.                 //更新 pre 等于 1
  29.                 } else {
  30.                     pre = 1;
  31.                 }
  32.                 down = 0;
  33.             //之前没有出现过下坡
  34.             } else {
  35.                 //将前一个小朋友的糖果数相加
  36.                 total += pre;
  37.                 //如果是上坡更新当前糖果数是上一个的加 1
  38.                 if (ratings[i] > ratings[i - 1]) {
  39.                     pre = pre + 1;
  40.                 //如果是平坡，更新当前糖果数为 1
  41.                 } else {
  42.                     pre = 1;
  43.                 }
  45.             }
  46.         } else {
  47.             down++;
  48.         }
  49.     }
  50.     //判断是否有下坡
  51.     if (down > 0) {
  52.         //和之前的逻辑一样进行相加
  53.         if (pre > down) {
  54.             total += count(down);
  55.             total += pre;
  56.         } else {
  57.             total += count(down + 1);
  58.         }
  59.     //将最后一个小朋友的糖果计算
  60.     } else {
  61.         total += pre;
  62.     }
  63.     return total;
  64. }
  66. //等差数列求和
  67. private int count(int n) {
  68.     return (1 + n) * n / 2;
  69. }

这个算法相对于解法一的好处就是将空间复杂度从 O(n) 优化到了 O(1)。

总

解法一虽然空间复杂度大一些，但是很好理解，正着遍历，倒着遍历的思想，每次遇到都印象深刻。解法二主要是对问题进行深入考虑，虽然麻烦些，但空间复杂度确实优化了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情