题目链接
LeetCode 135. 分发糖果[1]
题目描述
示例1
输入： [1,0,2] 输出： 5 解释： 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例2
输入： [1,2,2] 输出： 4 解释 ：你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
题解
这题虽然难度定义成困难，但其实代码不长，思路也比较简单清晰。
首先明确一下题目中的两个条件，我们可以把所有人的分数在坐标轴中连起来，这样就形成了一个波形图（图片来自官方题解）：
要注意的一点是图中 pt.13 那个位置也是一个谷底，因为它右边的分数等于它。
那么问题的关键就是如何找到这些谷底了。
两次遍历
首先初始化所有人都
分到 个糖果。
然后从左向右遍历一次所有分数，如果发现分数小于等于前一个人分数，那暂时不用管，因为你从左向右是没法知道下坡的点距离谷底还有多远的。而如果发现分数大于前一个人分数，那么就在前一个人糖果数基础上，再多分一个给他，因为是上坡，所以谷底一定在左边已经遍历过了，是知道距离的。
接着就是遍历下坡了，也就是从右向左遍历所有分数，同理如果发现分数大于后一个人分数，那么就在后一个人糖果数基础上，再多分一个给他。
但是这里要处理一个冲突，那就是峰顶既是上坡，又是下坡，其实只要两次遍历完取上坡和下坡中糖果数较大的那个就行了。
总结一下就是一次从左向右遍历所有上坡，一次从右向左遍历所有下坡，峰顶取两次较大值。
一次遍历
从上面方法中可以看出，本题求解的难点就在于从左向右遍历的时候，下坡到底有多长没法知道，必须全部遍历完了才能知道。还有就是山峰的值必须看左右两边的上坡下坡有多长。
为了解决这个问题，我们可以用变量 up 记录上坡的长度，down 记录下坡的长度。
当遇到谷底的时候，就表明一座山遍历结束了，那么我们只需要比较 up 和 down 的大小就知道峰顶取值了。
在具体实现的时候，这个方法细节有点多，一不小心就会错，直接看代码注释吧。
继续看下面这张图：
贴一段官方的样例解释：
单调栈
小结
第一种解法最容易理解和实现，也不用考虑什么特殊情况。但是后两种方法处理起来就稍稍有点麻烦了，需要结合样例和代码来理解。但是本质上都是一样的，都是从谷底（糖果数为 ）开始，向两周扩展。方法一是先从每个谷底向右边上坡扩展，再向左边下坡扩展。方法二是计算出相邻两个谷底之间的上坡下坡长度，然后直接计算。第三个方法是从每个谷底先向左边下坡扩展，再向右边上坡扩展。
代码
两次遍历（c++）
classSolution { public: intcandy(vector<int>&ratings) { intn=ratings.size(); vector<int>res(n, 1); for (inti=1; i<n; ++i) { if (ratings[i] >ratings[i-1]) { res[i] =res[i-1] +1; } } for (inti=n-2; i>=0; --i) { if (ratings[i] >ratings[i+1]) { res[i] =max(res[i], res[i+1]+1); } } returnaccumulate(res.begin(), res.end(), 0); } };
一次遍历（c++）
classSolution { public: intcount(intn) { returnn*(n+1)/2; } intcandy(vector<int>&ratings) { intn=ratings.size(); intsum=0; intup=0, down=0; intos=0, ns=0; for (inti=1; i<n; ++i) { ns=ratings[i]>ratings[i-1] ?1 : (ratings[i] <ratings[i-1] ?-1 : 0); // 这座山峰遍历结束，计算糖果数。 if ((os<0&&ns>=0) ||os>0&&ns==0) { // 这里看似好像峰顶没有加 1，其实是 count(down) 减去了 1。 // 因为谷底是共享的，所以将谷底给了下一座山峰的上坡。 sum+=count(up) +count(down) +max(up, down); up=down=0; } if (ns>0) up++; elseif (ns<0) down++; // 如果是平原，说明谷底不会共享，之前少加的 1 再补上。 else if (!ns) sum++; os=ns; } // 最后一座山峰循环里不会计算到，再加上。 sum+=count(up) +count(down) +max(up, down) +1; returnsum; } };
单调栈（c++）
classSolution { public: intcandy(vector<int>&ratings) { ratings.push_back(INT_MAX); intn=ratings.size(); vector<int>res(n, 1); stack<int>st; intsum=0; for (inti=0; i<n; ++i) { if (!st.empty() &&ratings[i] >=ratings[st.top()]) { while (!st.empty()) { intj=st.top(); st.pop(); if (j<n-1&&ratings[j] >ratings[j+1]) { res[j] =max(res[j], res[j+1]+1); } if (j>0&&ratings[j] >ratings[j-1]) { res[j] =max(res[j], res[j-1]+1); } sum+=res[j]; } } st.push(i); } returnsum; } };
参考资料
[1]
LeetCode 135. 分发糖果: https://leetcode-cn.com/problems/candy/
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
