文章目录

• 前言
• 一、题目
• 二、思路详解
• 三、搞点实际点儿的（C++实现）
• • 1.略显粗糙的代码实现
  • 2.稍显精致的代码实现
  • 3.最终的代码实现
  • 4.提交结果
• 总结

---

前言

      本文记录自己在LeetCode上关于一道算法题的解题过程，这道题花费了不少时间才通过。感觉在自己的这种解题风格道路上走远了！但是代码提交的结果还是比较满意的。 哈哈，过程比较曲折，下面为大家一一道来：

---

一、题目

      老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
      你需要按照以下要求，帮助老师给这些孩子分发糖果：

      要求1：每个孩子至少分配到 1 个糖果。
      要求2：评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。

      那么这样下来，老师至少需要准备多少颗糖果呢？

示例1：

输入：[1,0,2]
输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例2：

输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

该题所在网址：https://leetcode-cn.com/problems/candy/

二、思路详解

      瞧一瞧，看一看，大家品一下这个老师有多抠门~

      首先：给每个孩子至少给一个糖果，这个简单。要求 2 稍微难理解一点，参考下面这个示例来理解，概括为：如果一个孩子两侧，只要存在一个比他评分低的孩子，那么他的糖果数就要比这个低评分孩子的糖果要多。

这里给出一个示例：所有孩子的评分：{ 1,0,2,3,4,3,2,2 } 它对应的糖果数：{ 2,1,2,3,4,2,1,1 }。后面会对这个示例进一步分析。

      最开始的思路是这样的：按照平移的思想来设计，即；给起始第一个孩子1颗糖果，依次往后判断，如果比它大则糖果加1，比它小则减1，碰到相等的情况则另做分析。 最后将整体结果往上平移（可能有负数存在），使得最小糖果数为1即可。 但是后来发现不可行，逻辑判断太复杂，很难分析。 还有最重要的一点是，糖果数有时候会有一个突然的下降，比如给出的示例中评分为4和3的孩子，前者给4颗糖果，后者给2颗糖果。

      所以单纯的只从左到右的分析是不充分的，当然可以在这个基础上再改改，比如补充上从右到左进行分析，不过在这儿不聊这个。聊点清新脱俗的~

————————————————      华丽丽的分割线

      就糖果数突然有一个下降的现象，我思考了一下原因。从而得到一种解题思路：

      发现：如果能找到那些极小值点，也就是那些最终只分配 1 颗糖果的孩子（好惨！），因为给这些孩子的糖果数是已经确定的了。以此（这些糖果数）为基础，再对这些孩子的左右分别进行分析，很容易就可以确定他们的左右孩子应得的糖果数，然后依次迭代计算扩展至所有孩子。    将整个评分序列想象成为一个函数，接下来要做的是找到其中的极小值点，给它们分配糖果，再对其余的评分序列继续找当前的极小值点，分配糖果。直至分配结束。    想象一下快速排序的特点，每一次循环会确定一个最终排序结束时元素的位置。而目前的这个思路和它类似：每一次会确定若干个极小值点的糖果数。

      所以具体的算法思路如下：
      如果一个孩子的左右两侧评分都大于等于它，那么它就是一个极小值。
      (1) 找到所有极小值点，将它们对应的糖果数量置为1
      (2) 排除上述已经分配了糖果的孩子，在其余孩子中再次找极小值点，将它们对应的糖果数量置为2.（每一轮的极小值点分配的糖果数要比之前的多1个）
      (3) 不断重复步骤2. 直至给所有的孩子都分配了糖果。

      对上面的示例进行分析：给定孩子的评分数组为 { 1,0,2,3,4,3,2,2 }
      第一轮之后糖果数组为：_ 1 _ _ _ _ 1 1 ，其中第二个数 0 ，倒数第二个数 2 和最后一个数 2 为极小值。

      第二轮在第一轮的基础之上，得到两个孩子的评分区间分别为：{ 1 } 和 { 2,3,4,3} 。对这两个数组找它们的极小值，给这些极小值点的糖果数为2，得到第二轮之后糖果数组为：2 1 2 _ _ 2 1 1 ，其中区间 1 中唯一的一个数 1 是极小值，区间 2 中的第一个数 2 和最后一个数 3 为极小值。

      第三轮在第二轮的基础之上，得到一个孩子的评分区间分别为：{ 3,4} 。对这个数组找极小值，给这些极小值点的糖果数为3，得到第三轮之后糖果数组为：2 1 2 3 _ 2 1 1 ，其中第一个数 3 为最小值。

      第四轮在第三轮的基础之上，得到一个孩子的评分区间分别为：{ 4} 。对这个数组找极小值，给这些极小值点的糖果数为4，得到第四轮之后糖果数组为：2 1 2 3 4 2 1 1 ，这个唯一的数为极小值。

      糖果数：{ 2,1,2,3,4,2,1,1 }即为最终结果。

三、搞点实际点儿的（C++实现）

1.略显粗糙的代码实现

      说明：下面的代码有助于对整体思路的把控，并且我在代码中已经给出了详细的注释。缺点是太繁琐，提交的时候会报超时，我稍后会在此之上做一些优化。
      代码如下：

class Solution { private:int count; //用来计数int start; //每一轮循环的起始下标int end;//每一轮循环的结束下标int assignCandy;//每一轮应该给当前极小值点的糖果数int sum; //求和，用来返回最终结果 public:int candy(vector<int>& ratings) {int N = ratings.size();//为几个参数设置初始值count = 0;sum = 0;assignCandy = 1;start = 0;end = N - 1;int* flag = new int[N];//用来判断哪些孩子已经被分配了糖果，若分配了就置为1int* candys = new int[N];//保存给每一个孩子分配的糖果数目memset(flag, 0, sizeof(int)*N);//将flag数组初始时全置为0setCandy(ratings, flag, candys);//第一轮分配，找到本轮的极小值点，并进行糖果分配//在第一轮分配之后，这里采用循环结构来进行每一轮的糖果分配，count表示当前已经分配了糖果的孩子数目，//所以退出条件这里写作为 count<N while (count < N){assignCandy++;//每一轮待分配的糖果数量要比上一轮多1个for (int i = 0; i < N; i++)//遍历一遍数组，以上一轮找到的极小值点为基础，得到本轮应该分配糖果的孩子区间。{if (flag[i] == 0){start = i;while (i < N && flag[i] == 0)++i;end = i - 1;//每一次调用setCandy时，要先确定当前区间的start和end。setCandy(ratings, flag, candys); }}}for (int i = 0; i < N; i++)sum += candys[i]; //最后得到所有的糖果数目return sum;}void setCandy(vector<int>& temp, int flag[], int candys[]){if (start == end) //如果区间里只有一个数的情况，那它就是本轮的极小值，直接分配糖果并返回{candys[start] = assignCandy;flag[start] = 1;count++;return;}int i, prev, after;//判断区间的第一个数是否为极小值，只需要和第二个数相比较即可。 按照之前分析的，注意这里需要取等号。if (temp[start + 1] >= temp[start]){candys[start] = assignCandy;flag[start] = 1;count++;}//判断区间的最后一个数是否为极小值，只需要和倒数第二个数相比较即可。 按照之前分析的，注意这里需要取等号。if (temp[end] <= temp[end - 1]){candys[end] = assignCandy;flag[end] = 1;count++;}for (prev = start, i = start + 1, after = start + 2; i <= end - 1; ++i, ++after, ++prev){//对区间中间的所有数依次遍历，判断是否为极小值，按照之前分析的，注意这里需要取等号。if (temp[i] <= temp[prev] && temp[i] <= temp[after]){candys[i] = assignCandy;flag[i] = 1;count++;}}}};

      需要指出一点，也是之前困扰了我比较久的一个问题。上面这个代码，在while(count<N)循环中，有一行代码我之前是写成这样的：

...while (flag[i] == 0 && i < N)++i;...

      然后呢，它在VS2017中是可以编译并运行的，但是在LeetCode中会报错：“AddressSanitizer: heap-buffer-overflow on address…” ，个人猜测，在VS中对 && 应该是有做过优化的，而在LeetCode中是严格按照从左到右来判断的，所以会出现数组访问越界的现象。 解决方法：把 && 的左右互换一下就行。先判断 i<N 就好了。

---

2.稍显精致的代码实现

      上面这个代码因为在提交时会报超时，所以需要进行逻辑上的删减，去掉多余的部分。这次的代码采用递归来实现，我依然会给出详细的注释。
代码如下：

class Solution { private:int sum;//用来保存最终的糖果数，进行返回 public:int candy(vector<int>& ratings) {int N = ratings.size();sum = 0;int assignCandy = 1;//初始对每个极小值点分发的糖果数为1int start = 0; //第一轮循环的起始下标int end = N - 1; //第一轮循环的结束下标//这里就不需要 candys 和 flag 数组了哦setCandy(ratings, start, end, assignCandy); //递归方法调用return sum;}void setCandy(vector<int>& temp,int start,int end, int assignCandy){//注意：sum在 一旦找到当前轮次的极小值时，就会和当前的assignCandy相加，从而构成总的糖果数量。//如果区间长度为1的话，则它是一个极小值点，分配给它糖果，并将这个糖果数算在总数sum中。if (start == end){sum += assignCandy;return;}else if (start > end)//如果在两个极小值接连出现时，会出现这种情况， 直接返回即可，因为两个极小值之间没有元素了return;int i, prev, after;int startT = start, endT; //设置新的区间开始节点startT//处理第一个数，如果它是极小值的话if (temp[start + 1] >= temp[start]){sum += assignCandy;startT = start + 1;}for (prev = start, i = start + 1, after = start + 2; i <= end-1 ; ++i, ++after, ++prev){if (temp[i] <= temp[prev] && temp[i] <= temp[after]){sum += assignCandy;//一旦碰到一个极小值点，首先需要更新一下区间结束节点endTendT = i - 1;//对一个区间进行递归方法调用，注意待分配的糖果数要加1setCandy(temp, startT, endT, assignCandy + 1);//注意：这里可能会发生startT大于endT的现象//还需要设置下一个区间的开始节点startTstartT = i + 1;}}//处理最后一个数，如果它是极小值的话if (temp[end] <= temp[end - 1]){sum += assignCandy;endT = end - 1;}elseendT = end;//对一次循环中的最后一个区间进行分析setCandy(temp, startT, endT, assignCandy + 1);} };

---

3.最终的代码实现

      2 中的代码解决了 1 中存在的问题，但是它有一个缺点。
      当测试用例为{20000,19999,19998,19997，…，4，3，2，1}时，这样的逆序数组时，它的时间复杂度会急剧增大，是 2 中时间复杂度的 N 倍。所以，只好在 2 的基础上加上了关于逆序的判断；并且考虑到算法在完全升序排列的样本上时间复杂度会增大，趋于O(N2)，所以在加上关于升序的判断，这点可以参考快速排序的缺点。
      整体上代码的时间复杂度为O（lnN）,空间复杂度为O(lnN)，性能都还可以。得到最终的代码如下：

class Solution { private:int sum; public:int candy(vector<int>& ratings) {int N = ratings.size();sum = 0;int assignCandy = 1;int start = 0;int end = N - 1;setCandy(ratings, start, end, assignCandy);return sum;}void setCandy(vector<int>& temp,int start,int end, int assignCandy){if (start == end){sum += assignCandy;return;}else if (start > end)return;//如果区间中的元素是降序排列的，那么直接计算sum的值即可。 采用等差数列求和公式来计算。if (isSorted_descend(temp, start, end)) {int j = end - start; //j+1个数。int temp = (j + 1)*assignCandy + ((end-start)*(j + 1)) / 2;sum += temp;return;}else if (isSorted_ascend(temp, start, end)) //判断是否为升序{int j = end - start; //j+1个数。int temp = (j + 1)*assignCandy + ((end-start)*(j + 1)) / 2;sum += temp;return;}int i, prev, after;int startT = start, endT;if (temp[start + 1] >= temp[start]){sum += assignCandy;startT = start + 1;}for (prev = start, i = start + 1, after = start + 2; i <= end-1 ; ++i, ++after, ++prev){if (temp[i] <= temp[prev] && temp[i] <= temp[after]){sum += assignCandy;endT = i - 1;setCandy(temp, startT, endT, assignCandy + 1);startT = i + 1;}}if (temp[end] <= temp[end - 1]){sum += assignCandy;endT = end - 1;}elseendT = end;setCandy(temp, startT, endT, assignCandy + 1);}//判断当前区间的元素是否为降序排列。如果是，返回 1 如果两个元素相同，则认为非降序//结果为真表示是一个严格的降序序列int isSorted_descend(vector<int>& temp, int start, int end){while (start < end){if (temp[start] <= temp[start + 1])return 0;start++;}return 1;}//对是否是一个严格的升序序列的判定int isSorted_ascend(vector<int>& temp, int start, int end){while (start < end){if (temp[start] >= temp[start + 1])return 0;start++;}return 1;}};

4.提交结果

      以 3 中的代码进行提交，结果如图：

总结

      最终的代码实现整体上采用了递归的方法，也包含到了贪心和分治的思想。总算是按照自己的思路写完了，挺费劲的，道路是曲折的，但是结局是美好的~

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的LeetCode算法题0:分发糖果【贪心算法】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。