Leetcode基础算法篇|202409（4）贪心算法

贪心算法（Greedy Algorithm）：一种在每次决策时，总是采取在当前状态下的最好选择，从而希望导致结果是最好或最优的算法。

学习链接：leetcode-notes/docs/ch04/04.04/04.04.02-Exercises.md at main · datawhalechina/leetcode-notes · GitHub

贪心算法是一种改进的「分步解决算法」，其核心思想是：将求解过程分成「若干个步骤」，然后根据题意选择一种「度量标准」，每个步骤都应用「贪心原则」，选取当前状态下「最好 / 最优选择（局部最优解）」，并以此希望最后得出的结果也是「最好 / 最优结果（全局最优解）」。

贪心算法三步走

1. 转换问题：将优化问题转换为具有贪心选择性质的问题，即先做出选择，再解决剩下的一个子问题。
2. 贪心选择性质：根据题意选择一种度量标准，制定贪心策略，选取当前状态下「最好 / 最优选择」，从而得到局部最优解。
3. 最优子结构性质：根据上一步制定的贪心策略，将贪心选择的局部最优解和子问题的最优解合并起来，得到原问题的最优解。

例题：

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

思路：

### 初步思路

#### 1. 找到第一个谷底
首先，我们需要找到评分最低的孩子，并给他分配1个糖果。这个孩子就是我们所谓的“第一个谷底”。

#### 2. 找到下一个谷底
接下来，我们需要找到评分次低的孩子。如果这个孩子与上一个谷底相邻，我们需要比较他们的评分。评分更高的孩子应该获得比上一个谷底多1个糖果。如果不相邻，则直接分配1个糖果。

#### 3. 重复步骤2
继续这个过程，直到所有孩子都被分配糖果。

### 最终思路

在初步思路的基础上，我们发现可以通过两次遍历来简化问题：

1. **从左到右遍历**：确保每个孩子如果比左边的孩子评分高，则获得的糖果比左边的孩子多。
2. **从右到左遍历**：确保每个孩子如果比右边的孩子评分高，则获得的糖果比右边的孩子多。

### 最终思路的实现

class Solution(object):def candy(self, ratings):""":type ratings: List[int]:rtype: int"""n = len(ratings)candies = [1] * n  # 初始化每个孩子至少分配到 1 个糖果# 从左到右遍历，确保每个孩子如果比左边的孩子评分高，则获得的糖果比左边的孩子多for i in range(1, n):if ratings[i] > ratings[i - 1]:candies[i] = candies[i - 1] + 1# 从右到左遍历，确保每个孩子如果比右边的孩子评分高，则获得的糖果比右边的孩子多for i in range(n - 2, -1, -1):if ratings[i] > ratings[i + 1]:candies[i] = max(candies[i], candies[i + 1] + 1)# 返回所有孩子获得的糖果总数return sum(candies)

### 优越性

这种方法的优越性在于：
1. **时间复杂度低**：只需要两次遍历数组，时间复杂度为 `O(n)`，其中 `n` 是孩子的数量。
2. **空间复杂度低**：只需要一个长度为 `n` 的数组来存储每个孩子分配的糖果数量，空间复杂度为 `O(n)`。
3. **逻辑简单**：代码逻辑清晰，易于理解和维护。
4. **正确性高**：通过两次遍历，确保每个孩子获得的糖果数量满足题目要求，即每个孩子至少分配到1个糖果，且相邻两个孩子评分更高的孩子会获得更多的糖果。