LeetCode 1103. 分糖果 II

2023-05-06 HGNULB 约 8 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1103. 分糖果 II

题意分析

把 candies 颗糖按固定规则发给排成一排的 num_people 个人：第一次给第 1 个人 1 颗，第二次给第 2 个人 2 颗，……发到队尾就绕回第 1 个人继续，每次发的数量始终比上一次多 1。糖不够时，把剩下的全部给当前这个人然后结束。返回每个人最终拿到的糖果数。

题意里有两条容易读漏的规则。一是发放次数与人数无关，give 是一个只增不减的全局计数，绕回队首后不会重置成 1；二是结尾不是「跳过」而是「给光」，剩余糖果哪怕只有 1 颗也要发给当前轮到的人，不能因为不够 give 就丢掉。

约束给出 candies 最多 $10^9$、num_people 最多 1000。前者看着大，但因为每次发放量递增，总发放次数受 $1+2+\cdots+t \le candies$ 约束，$t$ 大约是 $\sqrt{2 \cdot candies}$，也就是四万多次——这个数量级明确告诉我们：直接按题意一次次发就够了，不需要任何加速。约束在这里不是难度信号，而是「放心暴力」的许可。

边界：candies 可能小到 1，此时第一个人拿走全部、其余人为 0；num_people 可能为 1，此时所有糖都堆给同一个人；糖果恰好在某轮发完（比如 candies = 1、candies = 3）时循环要能干净退出，不能多发一轮 0 颗。

解法：模拟发放

核心思路

这道题没有可挖掘的结构，答案完全由发放过程定义，所以思路的重点不是「怎么变快」，而是把过程压缩成尽量少的状态变量，让循环体不出错。

先确认暴力可行：上面已经算过，发放次数是 $O(\sqrt{candies})$ 级别，四万多次循环远在时限内。既然瓶颈不存在，就不必去推那套「先发满 k 整轮再处理零头」的等差数列公式——那种写法要解一个一元二次不等式并处理开方取整的边界，在面试白板上出错概率远高于收益。

除答案数组和剩余糖果外，只需维护 give：它既是本次理论发放量，也说明此前已经完成了 give - 1 次发放，所以当前收糖人的下标就是 (give - 1) % num_people。没有必要再维护一个与它始终相差 1 的计数器。

循环不变量是：每轮开始时，答案数组恰好记录前 give - 1 次发放，candies 是未发出的数量，当前应轮到 (give - 1) % num_people，理论上应发 give 颗。 取 min(candies, give) 作为实发量：糖充足时按规则发 give 颗；不足时一次发光。更新答案、剩余量并令 give++ 后，不变量继续成立。

这也给出正确性：每轮都把题意规定的下一次发放完整模拟出来，只有最后一次可能因余量不足而截断；退出时 candies == 0，所有糖恰好发出且没有额外发放。循环条件只需 candies > 0，是否发满一轮与终止无关。

解题步骤

准备答案数组：res = new int[num_people]，全 0 初始。用累加而非赋值，因为同一个人会在多轮里反复收糖，直接赋值会覆盖掉之前的量。

初始化 give = 1：它表示第一次理论上发 1 颗；此前完成次数自然是 give - 1 = 0。

循环条件 candies > 0：以「剩余糖果」而不是「人数」或「轮数」作为唯一出口，这样最后一轮发光后立即退出，不会多跑一次发 0 颗的空转。

定位收糖人：此前已完成 give - 1 次，所以当前下标为 (give - 1) % num_people。取模直接表达「走到队尾后回到队首」。

计算本次实发：cur = min(candies, give)。这一步同时覆盖了正常发放与糖果耗尽两种情形，是免去分支的关键。

同步更新：res[idx] += cur、candies -= cur、give++。答案必须加实发量 cur；发完后剩余量精确减少，下一轮理论发放量加 1。

返回 res。

若 candies = 0（虽然原题约束下至少为 1），循环一次也不会执行，直接返回长度为 num_people 的全 0 数组；代码不依赖“至少发放一次”这一前提。题目保证 num_people >= 1，因此取模不会除以 0。

以 candies = 10, num_people = 3 走一遍：

初始 res = [0,0,0]，candies = 10，give = 1。
第 1 轮：idx = (1-1) % 3 = 0，cur = min(10,1) = 1，res = [1,0,0]，剩 9。
第 2 轮：idx = (2-1) % 3 = 1，cur = min(9,2) = 2，res = [1,2,0]，剩 7。
第 3 轮：idx = (3-1) % 3 = 2，cur = min(7,3) = 3，res = [1,2,3]，剩 4。
第 4 轮：idx = (4-1) % 3 = 0，绕回队首；cur = min(4,4) = 4，res = [5,2,3]，剩 0。
candies = 0，循环退出，返回 [5,2,3]。

注意第 4 轮：give 是 4 而不是重新从 1 开始，这正是「发放次数全局递增」的体现；同时它恰好把糖发光，min 的两个参数相等，两条路径在此汇合。

再看一个不够发的例子 candies = 7, num_people = 4：前三轮发出 1、2、3 颗后剩 1，第 4 轮 give = 4 但 cur = min(1,4) = 1，第 4 个人只拿到 1 颗，res = [1,2,3,1]，循环结束。

代码实现

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int[] res = new int[num_people];
        for (int give = 1; candies > 0; give++) {
            int idx = (give - 1) % num_people;
            // 取较小值同时覆盖正常发放与最后一次发光两种情况。
            int cur = Math.min(candies, give);
            res[idx] += cur;
            candies -= cur;
        }

        return res;
    }
}

func distributeCandies(candies int, numPeople int) []int {
	res := make([]int, numPeople)
	for give := 1; candies > 0; give++ {
		idx := (give - 1) % numPeople
		// 取较小值同时覆盖正常发放与最后一次发光两种情况。
		cur := give
		if candies < cur {
			cur = candies
		}
		res[idx] += cur
		candies -= cur
	}

	return res
}

复杂度分析

时间复杂度：$O(num_people + \sqrt C)$，其中 C 是输入时的糖果数。初始化返回数组需要 $O(num_people)$；若共执行 t 次发放，则前 t-1 次完整发出的糖至少为 $t(t-1)/2 < C$，所以 $t = O(\sqrt C)$，每轮为常数操作。

空间复杂度：$O(num_people)$，来自必须返回的答案数组；除返回值外只使用常数个标量，为 $O(1)$。

关键点总结

看到「每次发的量固定递增」就该立刻估算发放次数是 $O(\sqrt{candies})$ 而不是 $O(candies)$，这个估算决定了「模拟是否可行」，是面试里必须主动说出来的一句话。

用 min(剩余, 应发) 在语义上统一「正常」与「收尾」两种情形；Java 可直接调用 Math.min，Go 用一个大小判断得到同一结果。

循环出口选「资源耗尽」而不是「轮数用完」，让终止条件与题意直接对应，边界自然正确。

give 已经隐含「完成次数为 give - 1」，所以位置直接用 (give - 1) % n；不维护重复状态，能从根源上避免两个计数器不同步。

答案数组要累加不能赋值，因为同一下标会被多轮命中。

面试视角：若面试官追问「能不能做到 $O(n)$」，可以答「能，先用等差数列求和解出能发满的完整次数 $k$，给每个人补上他在完整轮次里的等差和，再单独处理零头」，但要同时指出该写法需要解二次不等式并小心开方取整，收益仅从 $\sqrt{10^9}$ 降到 $n$，在本题约束下不划算——能讲清楚取舍比硬写公式更加分。

易错点总结

错误写法：答案累加理论发放量 give，而不是实发量 cur。用例 candies = 2, num_people = 1：两轮会记成 1 + 2 = 3，凭空多发 1 颗；正确答案是 [2]。

错误写法：绕回队首时把 give 重置为 1。用例 candies = 10, num_people = 3：第 4 轮会只发 1 颗，得到 [2,2,3] 外加剩余 3 颗继续发放，答案与期望的 [5,2,3] 完全不同。

错误写法：最后一次执行 res[idx] += candies 后，既不 break 也不把 candies 清零。用例 candies = 7, num_people = 4：发完最后 1 颗后剩余量仍是 1，循环会继续拿同一颗糖发放，最终总数超过 7。

错误写法：res[idx] = cur 用赋值代替累加。用例 candies = 10, num_people = 3：第 4 轮给 0 号位赋 4，把第 1 轮的 1 颗覆盖掉，得到 [4,2,3]，总数只有 9。

错误写法：循环条件写成 candies >= give。用例 candies = 7, num_people = 4：剩 1 颗而 give = 4 时循环提前退出，最后 1 颗糖没人拿到，返回 [1,2,3,0]。

错误写法：用 give <= num_people 作为循环条件。用例 candies = 10, num_people = 3：只发 3 轮就停，剩下 4 颗糖凭空消失，返回 [1,2,3]。

错误写法：把 idx 算成 give % num_people。用例 candies = 10, num_people = 3：give 从 1 起算而下标从 0 起算，整体错位一位，第一次发放会落到 1 号位而不是 0 号位；正确公式是 (give - 1) % num_people。

错误写法：认为 num_people = 1 需要特判。用例 candies = 6, num_people = 1：取模恒为 0，主逻辑天然正确地把 1+2+3 全累加到同一个人身上，额外的特判分支只会增加出错面。

错误写法：用等差数列公式时忽略「最后一轮可能只发满一部分人」。用例 candies = 10, num_people = 3：完整轮数算错会把第 4 次发放当成新一整轮，给每个人都补上一份，结果严重偏大。

相似题目

题目	难度	考察点
135. 分发糖果	困难	同样是分糖但改为满足相邻约束的最小总量，需左右两次贪心扫描
575. 分糖果	简单	只关心种类数与半数的较小值，是纯计数题，不涉及发放顺序
1431. 拥有最多糖果的孩子	简单	先求最大值再逐个比较，练习「一次预处理 + 一次判断」的两遍扫描
860. 柠檬水找零	简单	同为按序模拟资源收支，但每步要在多种面额里贪心选择找零方案
874. 模拟行走机器人	中等	状态换成坐标与朝向，取模用于方向数组循环，还要配合哈希集合判障碍
621. 任务调度器	中等	表面是逐轮模拟，实际可用桶思想直接推公式，与本题的模拟取舍相对照