面试经典150题 P135 分发糖果

---

时间轴

时间轴

2025-10-20

init

贪心

---

题目：

P135 分发糖果

https://leetcode.cn/problems/candy/description/?envType=study-plan-v2&envId=top-interview-150

可以想象 ratings 构成一段连绵的山，最开始我们初始化为 1，是平坦的平地，从左向右扫描会处理上坡的所有元素，从右向左扫描处理下坡的元素，而对于上下坡的分界点，要由左边要求的和右边要求的最大值+1，才能既满足上坡，又满足下坡。

初始化先给每一个人发一个糖果。

🍬 Step 1：从左到右保证右边比左边高的孩子糖果更多：

if (ratings[i] > ratings[i-1])
    candy[i] = candy[i-1] + 1

🍬 Step 2：从右到左

保证左边比右边高的孩子糖果更多，同时和已有值取最大（避免破坏左到右的规则）：

if (ratings[i] > ratings[i+1])
  candy[i] = max(candy[i], candy[i+1] + 1)

• 上坡从左往右，因为右边需要参考左边
• 下坡从右往左，因为左边需要参考右边

代码：

#include <numeric>
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
	int candy(vector<int> &ratings)
	{
		int i, n = ratings.size();

		vector<int> candies(n, 1);
		// left to right
		for (i = 1; i < n; i++) {
			if (ratings[i] > ratings[i - 1]) {
				candies[i] = candies[i - 1] + 1;
			}
		}
		// right to left
		for (i = n - 2; i >= 0; i--) {
			if (ratings[i] > ratings[i + 1]) {
				candies[i] = std::max(candies[i + 1] + 1,
						      candies[i]);
			}
		}

		return std::accumulate(candies.begin(), candies.end(), 0);
	}
};