力扣每日一题——分发糖果
目录
题目链接：135. 分发糖果 - 力扣（LeetCode）
题目描述
解法一：两次遍历贪心法
Java写法：
C++写法：
运行时间
时间复杂度和空间复杂度
时间复杂度：O(n)
空间复杂度：O(n)
总结
题目链接：135. 分发糖果 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2] 输出：5 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2：
输入：ratings = [1,2,2] 输出：4 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
提示：
n == ratings.length1 <= n <= 2 *0 <= ratings[i] <= 2 *
解法一：两次遍历贪心法
这道题目的核心就是给一排孩子分糖果，要求每个孩子至少一颗，而且相邻的两个孩子里，评分更高的那个必须拿到更多糖果。咱们的目标是用最少的糖果数满足这些条件。解题思路其实挺直观的，就是用两次遍历来调整糖果分配，下面我分段讲讲具体怎么操作。
首先，先给每个孩子都发一颗糖，这是最基本的，因为题目要求每人至少一个。这样初始化后，咱们就有了一个起点，后面再根据评分高低来额外加糖。这一步很简单，但很重要，它确保了最低要求被满足，后续调整都在这个基础上进行。
接着，从左往右遍历一遍孩子。这次只看每个孩子和他左边邻居的关系：如果当前孩子的评分比左边的高，那他的糖果就得比左边的多一颗。比如左边孩子有2颗糖，他就得拿3颗。这样遍历完，就能保证所有“右边比左边评分高”的情况都满足了，但这时候“左边比右边评分高”的情况可能还没处理好，因为这次遍历只考虑了左邻居。
然后，从右往左再遍历一遍。这次只看每个孩子和他右边邻居的关系：如果当前孩子评分比右边的高，那他的糖果应该比右边的多。但这里有个关键点——不能直接设成“右边糖果数+1”，因为可能从左往右遍历时已经给他分配了更多糖（比如因为左边邻居的关系）。所以要用max函数，比较当前已有的糖果数和“右边糖果数+1”，取更大的那个。这样既不会破坏第一次遍历的结果，又能确保右边条件也满足。
最后，把每个孩子手里的糖果数加起来，就是最少需要的总数了。这个方法之所以高效，是因为它分两次处理了相邻关系，每次只专注一侧（先左后右），通过max操作协调冲突，避免重复发糖或者遗漏条件。整体上，时间复杂度是O(n)，空间上用了额外数组，但很实用。
Java写法：
public class Solution {public int candy(int[] ratings) {if (ratings == null || ratings.length == 0) return 0;int n = ratings.length;int[] candies = new int[n];Arrays.fill(candies, 1); // 初始化每人至少1颗糖果// 从左到右遍历：确保右侧高分孩子糖果 > 左侧for (int i = 1; i < n; i++) {if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;}}// 从右到左遍历：确保左侧高分孩子糖果 > 右侧，并取max保证两边条件for (int i = n - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candies[i] = Math.max(candies[i], candies[i + 1] + 1);}}// 计算总糖果数int total = 0;for (int num : candies) {total += num;}return total;}
}C++写法：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int candy(vector<int>& ratings) {int n = ratings.size();if (n == 0) return 0;vector<int> candies(n, 1); // 初始化每人至少1颗糖果// 从左到右遍历：确保右侧高分孩子糖果 > 左侧for (int i = 1; i < n; i++) {if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;}}// 从右到左遍历：确保左侧高分孩子糖果 > 右侧，并取maxfor (int i = n - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candies[i] = max(candies[i], candies[i + 1] + 1);}}// 计算总糖果数int total = 0;for (int num : candies) {total += num;}return total;
}int main() {vector<int> ratings = {1, 2, 2}; // 示例输入cout << "最少糖果数: " << candy(ratings) << endl; // 输出 4return 0;
}运行时间
时间复杂度和空间复杂度
时间复杂度：O(n)
- 原因：算法仅需两次独立遍历数组：
- 从左到右遍历：检查每个孩子与左邻居的评分关系，若评分更高则糖果数+1。
- 从右到左遍历：检查每个孩子与右邻居的评分关系，若评分更高则更新糖果数为
max(当前值, 右邻居糖果数+1)。
- 每次遍历耗时 O(n)，总时间复杂度为 O(n)。
空间复杂度：O(n)
- 原因：需要额外长度为
n的数组candies存储每个孩子的糖果数。
总结
本文介绍了LeetCode题目"分发糖果"的贪心解法。题目要求给一排孩子分糖果，满足每个孩子至少1颗且相邻孩子中评分高的糖果更多。解法采用两次遍历：第一次从左到右确保右高分孩子糖果更多，第二次从右到左处理左高分情况并用max函数维持条件。Java和C++实现均使用O(n)时间和空间复杂度，其中空间开销用于存储糖果分配数组。该方法高效协调了相邻关系，确保最少糖果数的同时满足题目所有条件。