冠军资讯
代码一只喵在算法面试中，力扣（LeetCode）的 135 题《分发糖果》是一道经典的题目。问题描述是：有 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给每个孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 相邻两个孩子评分更高的孩子，必须获得更多的糖果。
求最少需要准备多少糖果？这个题目看似简单，实则蕴含着贪心算法的思想，如果处理不当，很容易陷入局部最优解。
贪心算法与局部最优解
解决分发糖果问题的核心在于如何保证相邻孩子之间的糖果数量关系。简单的思路是从左到右扫描一次，如果右边的孩子评分高于左边的孩子，则右边的孩子糖果数加 1。但这种方法只能保证部分情况，例如 [1, 0, 2]，按照这个思路会得到 [1, 1, 2]，但实际上应该是 [2, 1, 2]。
正确的贪心策略是进行两次扫描：
- 从左向右扫描，确保每个孩子比左边的孩子评分高时，糖果数多 1。
- 从右向左扫描，确保每个孩子比右边的孩子评分高时，糖果数多 1。注意，这里需要取当前糖果数和右边孩子糖果数 + 1 的最大值。
这种两次扫描的方式保证了每个孩子都满足题目要求，并且总的糖果数最少。
详细的原理剖析
两次扫描可以避免陷入局部最优解。第一次扫描保证了所有“上升”的序列满足条件，第二次扫描则修正了所有“下降”的序列。举例来说，数组 [1, 2, 87, 87, 87, 2, 1]。第一次扫描后，糖果分配可能是 [1, 2, 3, 1, 1, 1, 1]。第二次扫描可以修正分配，保证所有孩子都满足要求。最终的分配应该是 [1, 2, 3, 2, 1, 2, 1]。
分发糖果的代码实现（Java）
下面是使用 Java 实现的解决方案：
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1); // 初始都分配一个糖果
// 从左向右扫描
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// 从右向左扫描
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 totalCandies = 0;
for (int candy : candies) {
totalCandies += candy;
}
return totalCandies;
}
}
实战避坑经验与性能优化
- 数组越界问题：在扫描数组时，务必注意边界条件，避免数组越界异常。可以使用
i > 0和i < n - 1来进行判断。 - 空间复杂度优化：虽然上面的代码使用了一个额外的数组
candies，空间复杂度为 O(n)，但在某些情况下，可以通过原地修改输入数组来降低空间复杂度。不过，这种方法会修改输入数据，需要根据实际情况考虑。 - 性能测试：针对大规模输入数据进行性能测试，可以发现潜在的性能瓶颈。例如，可以使用 JMH (Java Microbenchmark Harness) 进行微基准测试。
- 代码可读性：编写清晰易懂的代码至关重要。添加必要的注释，使代码更易于理解和维护。
深入讨论：与其他算法思想的结合
分发糖果问题体现了贪心算法的思想，但也可以与其他算法思想结合使用。例如，可以使用动态规划的思想来解决类似的分配问题。在实际项目中，算法的选择往往取决于具体的业务场景和性能要求。
此外，在实际的生产环境中，我们经常使用类似 Nginx 的反向代理服务器来做负载均衡，应对高并发的场景。Nginx 可以根据不同的策略（例如轮询、IP Hash 等）将请求分发到不同的后端服务器，从而提高系统的整体性能和可用性。为了更好地管理 Nginx，我们可以使用宝塔面板等工具，简化配置和维护工作。同时，我们需要关注 Nginx 的并发连接数，并根据实际情况进行调整。
