Java 中的糖果分配问题

这是一个在 Google、Amazon、TCS、Accenture 等顶级 IT 公司的面试中经常问到的问题。通过解决这个问题，面试官想检查面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将使用不同的方法和逻辑解决糖果分配问题。同时，我们还将为此创建 Java 程序。

问题陈述

问题指出，向 N 个孩子分发最少数量的糖果，以满足以下条件：

• 每个孩子必须至少有一颗糖果。
• 排名较高的孩子将比他们的邻居获得更多的糖果。

请注意，每个孩子都有一个排名。任务是您必须分发的最少糖果数量。

让我们通过一个例子来理解这个问题。

示例 1

假设有四个孩子 A、B、C 和 D，他们的排名分别为 1、2、3 和 4。

让我们一个接一个地分发糖果给每个孩子。

让我们看另一个例子。

示例 2

假设有四个孩子 A、B、C 和 D，他们的排名分别为 4、3、2 和 1。

第一轮，我们将给每个孩子分发 1 颗糖果。

我们观察到孩子 A 和孩子 B 的糖果数量相同，而孩子 A 的排名高于孩子 B。因此，这违反了条件。所以，我们将再分发 1 颗糖果给孩子 A。

我们观察到孩子 A 和 B 满足条件，但孩子 B 和 C 不满足条件。因为 B 和 C 是邻居，并且各有 1 颗糖果。不同排名但拥有相同数量糖果是不允许的。所以，我们将再分发 1 颗糖果给孩子 B。

我们再次观察到孩子 A 和 B 的糖果数量相同，而孩子 A 的排名高于孩子 B。所以，我们将再分发 1 颗糖果给孩子 A。

我们观察到孩子 A 和 B 满足条件，但孩子 C 和 D 不满足条件。因为 C 和 D 是邻居，并且各有 1 颗糖果。不同排名但拥有相同数量糖果是不允许的。所以，我们将再分发 1 颗糖果给孩子 C。

我们再次观察到孩子 B 和 C 的糖果数量相同，而孩子 B 的排名高于孩子 C。所以，我们将再分发 1 颗糖果给孩子 B。

我们观察到孩子 A 和 B 的糖果数量相同，而孩子 A 的排名高于孩子 B。因此，这违反了条件。所以，我们将再分发 1 颗糖果给孩子 A。

现在，我们已经根据问题中指定的条件分发了糖果。因此，我们需要 10 颗（4 + 3 + 2 + 1）糖果分发给每个孩子。

在上面两个例子中，孩子的排名已经排序。那么，如果排名不是有序的怎么办？

特殊情况

考虑以下孩子排名的排列。

1, 2, 6, 5, 4, 3, 1

给每个孩子分发 1-1 颗糖果。

我们观察到孩子 B 的排名高于孩子 A，但糖果数量相同，这是不公平的。所以，我们将再分发 1 颗糖果给孩子 B。

我们观察到孩子 C 的排名高于孩子 B，但孩子 B 的糖果比孩子 C 多，这是不公平的。所以，我们将再分发 1 颗糖果给孩子 C。

我们观察到孩子 B 和 C 的糖果数量相同，而孩子 C 的排名更高，所以这是不公平的。再给孩子 C 分发 1 颗糖果。

这里需要注意的是，孩子 D、E、F 和 G 的排名分别为 5、4、3 和 1，呈递减顺序。这些排列永远不会形成一个好的排列。因此，在这种情况下，首先，以从左到右和从右到左的方式分发糖果。之后，取两个数组中的最大值。

从左到右 1, 2, 3, 1, 1, 1, 1

从右到左 1, 1, 5, 4, 3, 2, 1

两个数组中的最大值 1, 2, 5, 4, 3, 2, 1

因此，最终的分配将是 1, 2, 5, 4, 3, 2, 1。因此，我们至少需要 18 颗（1 + 2 + 5 + 4 + 3 + 2 + 1）糖果进行分配。

问题解决方案

这个问题可以通过以下四种方法解决

• 使用暴力破解法
• 使用两个数组
• 使用一个数组
• 常数空间单次遍历法

使用暴力破解法

这是解决问题最简单的方法。在这种方法中，我们使用了 1D 数组。一个名为 candies 的数组跟踪分发给孩子的糖果数量。最初，我们给每个孩子分发一颗糖果。之后，开始从左到右遍历数组。在遍历数组期间，我们检查以下内容：

• 如果当前元素（第 i 个）的排名（ranking[i]）大于前一个元素的排名（ranking[i-1]），并且 candies[i] 小于或等于 candies[i-1]，则将当前元素（第 i 个）的糖果数量更新为 candies[i - 1] + 1。

因此，当前和前一个元素的糖果分配变得符合问题陈述中指定的条件。

在上述步骤中，我们已经检查了当前元素与前一个元素。现在，我们将在同一步骤中，也检查当前元素与下一个元素。

• 如果当前元素（第 i 个）的排名（ranking[i]）大于下一个元素的排名（ranking[i+1]）为真，则将当前元素的糖果数量更新为 candies[i + 1] + 1。

对整个排名数组重复上述条件。

如果上述跟踪没有更新 candies[] 数组中的糖果数量，这意味着我们得到了最终的糖果分配。此时，我们不应该继续跟踪数组。为了跟踪数组的更新，我们使用了布尔变量 hasChanged，它最初设置为 true。

最后，求和 candies[] 数组的元素。它给出了分发所需的最小糖果数量。

让我们在 Java 程序中实现上述逻辑。

DistributeCandy1.java

输出

The minimum number of candies require to distribute is: 18

复杂度分析

对于上述方法，时间复杂度为 O(n²)。因为我们最多遍历了数组 n 次，并且它们的糖果计数将在每次遍历中更新一次。上述方法的空间复杂度为 O(n)，因为我们没有使用任何额外的空间。

使用两个数组

在此方法中，我们使用了两个数组（left2right 和 right2left）。这两个数组分别存储了当前孩子在考虑其左右邻居分布时所需的糖果数量。

对于 left2right 数组，我们假设了以下分配规则：

排名高于左邻居的孩子总是应该比左邻居获得更多的糖果。

对于 right2left 数组，我们假设了以下分配规则：

排名高于右邻居的孩子总是应该比右邻居获得更多的糖果。

最初给每个孩子分发 1 颗糖果，就像我们之前的方法一样。为此，我们通过调用 Arrays.fill() 方法将数组填充为 1。

之后，开始遍历数组。首先，我们对 left2right 数组进行遍历。

如果当前元素（第 i 个）的排名大于其左邻居，则将 left2right 数组中当前元素的糖果数量更新为 left2right[i-1] + 1。因此，我们看到在更新之前，当前孩子的糖果数量总是小于或等于其邻居的糖果数量。

由于在更新之前，当前元素（孩子）的糖果数量总是小于或等于其左邻居的糖果数量。

遍历完 left2right 数组后，遍历 right2left 数组。如果当前孩子 (i) 的排名大于其右邻居 (i+1)，则将当前元素更新为 right2left[i + 1] + 1。

当我们完成两次遍历（从左到右和从右到左）后，在两个数组中找到最大元素。因为它满足左右邻居关系。找到 max(left2right, right2left) 后得到的数组是每个孩子拥有的糖果数量。最后，求和数组以找到分发所需的最小糖果数量。

上述功能也可以用数学函数表示如下：

其中 n 表示排名数组的长度。

让我们在 Java 程序中实现上述逻辑。

DistributeCandy2.java

输出

The minimum number of candies require to distribute is: 28

复杂度分析

上述方法的时间复杂度为 O(n)，因为我们遍历了 left2right 和 right2left 数组三次。上述方法的空间复杂度为 O(n)，因为没有使用额外的空间。

使用一个数组

这种方法与前一种方法非常相似。唯一的区别在于我们使用的数组数量。以前，我们使用了两个数组，这使得代码更复杂且需要更多内存。

为了减少这个问题，我们使用了一个名为 candies[] 的单个数组，它跟踪要分发给当前孩子的糖果数量。

因此，在这种方法中，我们也将给每个孩子分发 1 颗糖果。之后，开始从左到右遍历排名数组，并且只考虑与左邻居相关的分布。

这意味着，如果当前元素（第 i 个）的排名大于其左邻居，并且糖果数量小于或等于，则将 candies[] 数组中当前孩子的糖果数量更新为 candies[i-1] + 1。

注意：在更新数组时，不要将当前元素 (candies[i]) 与前一个元素 (candies[i-1]) 进行比较，因为在更新之前 candies[i] <= candies[i - 1]。

之后，以从右到左的方式遍历排名数组。为了满足左右邻居关系，我们需要更新第 i 个元素的糖果。

在向后遍历时，如果 ranking[i] > ranking[i+1]，则只考虑右邻居条件。我们不需要将当前元素的糖果数量更新为 candies[i+1]+1。

仅当 candies[i] <= candies[i+1] 时才更新当前元素的糖果数量。

这是因为这次我们已经在从左到右遍历期间更新了糖果数组。因此，candies[i] 不一定小于或等于 candies[i + 1]。

因此，如果 ranking[i] > ranking[i + 1]，我们可以将 candies[i] 更新为 max(candies[i], candies[i + 1] + 1)，这使得 candies[i] 同时满足左邻居和右邻居条件。

当我们完成两次遍历（从左到右和从右到左）后，找到两次遍历的最大元素组合。因为它同时满足左邻居和右邻居关系。找到 max(candies[i], candies[i+1]+1) 后得到的数组是每个孩子拥有的糖果数量。最后，求和 candies[] 数组以找到分发所需的最小糖果数量。

上述功能也可以用数学函数表示如下：

其中 n 表示排名数组的长度。

让我们在 Java 程序中实现上述逻辑。

DistributeCandy3.java

输出

The minimum number of candies require to distribute is: 21

复杂度分析

上述方法的时间复杂度为 O(n)，因为我们遍历了糖果数组三次。上述方法的空间复杂度为 O(n)，因为没有使用额外的空间。

常数空间单次遍历法

这种方法与前三种方法不同。它依赖于观察。为了根据问题陈述分配糖果，总是以 1 的增量分配糖果。每个孩子将获得的最少糖果数量是 1。因此，在这种情况下，分配可能采用 1、2、3、...、n 或 n、...、3、2、1 的形式。我们可以将这些糖果数量相加，得到要分配的最小糖果数量。这可以通过以下数学公式实现：

现在，我们可以看到给定排名可能呈递增或递减顺序。每当排名斜率上升时，分配将采用 1、2、3、...、m 的形式。另一方面，下降斜率将采用 k、...、3、2、1 的形式。

这里出现了一个挑战，即局部峰值点只能包含在上升或下降斜率中的一个。所以，我们必须决定将局部峰值点 (n) 包含在哪一个斜率中。

峰值点应该是根据上升和下降斜率确定的计数中的最大值，它同时满足左右邻居条件。为了确定分配所需的糖果数量，峰值点应该包含在包含更多点的斜率中。

让我们看看这种方法的实现。

在下面的 Java 程序中，我们使用了两个变量 oldSlope 和 newSlope，它们用于确定峰值和谷值的出现。为了跟踪上升和下降斜率上元素的计数，我们分别定义了另外两个变量 up 和 down。请注意，这里我们没有包含峰值元素。

在下降斜率结束时更新糖果的总计数。如果排名处于点的水平，表示图中的山脉末端。当我们到达山顶时，确定我们将峰值点包含在哪里。可以通过比较变量 up 和 down 以及到该点的总和来确定。

因此，分配给峰值元素的计数变为 max(up, down) + 1。此时，重置 up 和 down 变量，表示新的山脉的开始。

下图显示了此示例需要处理的情况：

排名：[1 2 3 4 5 3 2 1 2 6 5 4 3 3 2 1 1 3 3 3 4 2]

让我们在 Java 程序中实现上述方法。

DistributeCandy4.java

输出

The minimum number of candies require to distribute is: 20

复杂度分析

上述方法的时间复杂度为 O(n)，因为我们遍历了排名数组一次。上述方法的空间复杂度为 O(1)，因为我们使用了额外的空间。