力扣（分发糖果）-EW帮帮网

解析 LeetCode 135. 分发糖果：两次遍历的贪心策略

一、题目分析

在这里插入图片描述

（一）问题定义

给定表示孩子评分的数组 ratings，需给每个孩子分发糖果，满足：

每个孩子至少 1 颗糖果。
相邻孩子中，评分高的孩子糖果数更多。
目标是求出最少需要准备的糖果总数。

（二）核心挑战

如何在满足规则的前提下，让糖果总数最少。这意味着不能简单地给每个评分高的孩子随意多分配糖果，而要通过合理的策略，在保证规则的同时，尽可能复用已有的糖果分配，避免冗余。

二、算法思想：两次遍历的贪心策略

（一）贪心策略的分步实现

贪心算法的核心是每一步都做出局部最优选择，最终期望得到全局最优。本题中，由于需要同时满足“左相邻”和“右相邻”的规则（即对于一个孩子，要同时比左边评分低的多，比右边评分低的多），一次遍历无法兼顾，因此采用两次遍历：

第一次遍历（从左到右）：处理每个孩子与左边相邻孩子的关系。若当前孩子评分高于左边，那么其糖果数为左边孩子糖果数 + 1；否则保持至少 1 颗（初始化已保证）。这样能确保满足“左边相邻评分低的孩子糖果少”的规则。
第二次遍历（从右到左）：处理每个孩子与右边相邻孩子的关系。若当前孩子评分高于右边，此时需要比较当前已分配的糖果数和右边孩子糖果数 + 1，取较大值（因为要同时满足左边和右边的规则，必须保证比两边评分低的都多）。这一步确保满足“右边相邻评分低的孩子糖果少”的规则。

通过两次遍历，分别处理左右相邻的约束，最终得到满足所有条件的最少糖果分配。

（二）局部最优到全局最优的推导

第一次遍历的局部最优：保证每个孩子在“左相邻”关系中，评分高的得到更多糖果，此时得到的是仅满足左相邻规则的局部最优分配。
第二次遍历的局部最优：在第一次的基础上，保证每个孩子在“右相邻”关系中，评分高的得到更多糖果，此时修正后的分配同时满足左右相邻规则，最终实现全局最优（糖果总数最少）。

两次局部最优的选择，共同达成了全局满足规则且糖果总数最少的目标。

三、代码实现与详细解析

class Solution {
    public int candy(int[] ratings) {
        // 初始化每个孩子的糖果数为 1，满足“至少 1 颗”的基本要求
        int[] childSuger = new int[ratings.length];
        Arrays.fill(childSuger, 1); 
        
        // 第一次遍历：从左到右，处理与左边相邻孩子的关系
        for (int len = 1; len < ratings.length; len++) { 
            // 若当前孩子评分高于左边相邻孩子
            if (ratings[len - 1] < ratings[len]) { 
                // 当前孩子糖果数 = 左边孩子糖果数 + 1
                childSuger[len] = childSuger[len - 1] + 1; 
            }
        }
        // 第二次遍历：从右到左，处理与右边相邻孩子的关系
        for (int len = ratings.length - 2; len >= 0; len--) { 
            // 若当前孩子评分高于右边相邻孩子
            if (ratings[len + 1] < ratings[len]) { 
                // 取“当前已分配糖果数”和“右边孩子糖果数 + 1”的较大值，保证同时满足左右规则
                childSuger[len] = Math.max(childSuger[len], childSuger[len + 1] + 1); 
            }
        }
        // 计算糖果总数：遍历累加每个孩子的糖果数
        int sumSuger = 0; 
        for (int sugerNum : childSuger) { 
            sumSuger += sugerNum; 
        }
        return sumSuger; 
    }
}

（一）代码流程拆解

初始化糖果数组：创建 childSuger 数组，用 Arrays.fill 将每个元素初始化为 1，确保每个孩子至少 1 颗糖果。
第一次遍历（左到右）：从索引 1 开始遍历（因为要和左边孩子比较），若当前孩子评分高于左边，就将其糖果数设为左边孩子糖果数 + 1，这样保证了左边相邻的规则。
第二次遍历（右到左）：从索引 ratings.length - 2 开始遍历（和右边孩子比较），若当前孩子评分高于右边，就取当前糖果数和右边孩子糖果数 + 1 中的较大值。这一步是为了在第一次遍历的基础上，修正右边相邻的规则，确保同时满足左右两边。
计算总数：遍历 childSuger 数组，累加得到糖果总数并返回。

（二）关键逻辑解析

两次遍历的必要性：由于需要同时满足左右相邻的规则，一次遍历无法同时处理两个方向的约束。两次遍历分别处理左和右，通过分步优化，最终满足所有条件。
Math.max 的作用：在第二次遍历中，当当前孩子评分高于右边时，不能直接赋值为 childSuger[len + 1] + 1，因为第一次遍历可能已经给当前孩子分配了更多的糖果（比如同时满足左边更高的情况）。所以需要取较大值，保证既满足右边规则，又不破坏左边已经满足的规则，从而实现全局最优。

四、复杂度分析

（一）时间复杂度

两次遍历数组：第一次遍历 for (int len = 1; len < ratings.length; len++) ，第二次遍历 for (int len = ratings.length - 2; len >= 0; len--) ，每次遍历的时间复杂度都是 $O (n)$ （n 是 ratings 数组长度）。
最后累加糖果总数的遍历，时间复杂度也是 $O (n)$ 。
总体时间复杂度为 $O (n)$ ，线性时间复杂度保证了算法的高效性。

（二）空间复杂度

额外使用了 childSuger 数组，其长度为 n ，所以空间复杂度为 $O (n)$ 。如果想优化空间复杂度，理论上可以不用数组，但若要严格遵循题目要求记录每个孩子的糖果数，这种空间开销是必要的。

力扣（分发糖果）