塔的高度之间的最小差异？

Question

我正在经历一些面试问题，我看到了这个

给定 n 个塔的高度和值 k。您必须将每个塔的高度增加或减少 k。您需要最小化最长和最短塔的高度之间的差异并输出该差异。

我想答案会是 (maxheight-k) - (minheight + k)。我试过一些测试用例，它运行良好。

但我不确定，我想我错过了一些东西，是吗？

Answer 1

m7thon 的回答解释了您的解决方案的问题，所以我只会解释您如何实际解决这个问题。. .

需要注意的重要事情是，对于任何给定的塔，如果您选择将其高度从h _i增加到h _i  +  k，那么您不妨增加所有较短塔的高度：这不会影响最大值（因为如果h _j  <  h _i，则h _j  +  k  <  h _i  +  k），并且可以通过增加最小值来提供帮助。相反，如果你选择减少从塔的高度^ h_我要^ h_我 ？ 克，那么您不妨降低所有较高塔的高度。

因此，虽然有 2 ^{n 种}可能的方法来选择应该增加还是减少哪些塔，但我们实际上可以忽略其中的大部分。有些塔将是我们增加高度的最高塔；对于所有较短的塔，我们也将增加它们的高度，对于所有较高的塔，我们将降低它们的高度。因此，只有n 种 有趣的方法可以选择应该增加还是减少哪些塔：一种是每个塔成为我们增加高度的最高塔的机会。

[学究注#1：您可能会注意到降低所有塔的高度也是有效的，在这种情况下没有这样的塔。但这等效于增加所有塔的高度——无论我们在每个高度上加k还是从每个高度减去k ，无论哪种方式，我们实际上都没有改变 max-minus-min。]

[学究注#2：我只提到了“较短的塔”和“较高的塔”，但也有可能多个塔具有相同的初始高度。但这种情况并不重要，因为我们不妨全部增加或全部减少——增加一些并减少其他人是没有意义的。所以这里描述的方法仍然可以正常工作。]

所以，让我们从对原始高度进行排序并按升序编号开始，以便h ₁是原始最短塔的原始高度，而h _n是原始最高塔的原始高度。

对于每个i，尝试第i个最短的塔是我们增加高度的最高塔的可能性；也就是说，尝试我们增加h ₁到h _i并减少h _{i +1}到h _n的可能性。有两组情况：

• 如果i  <  n，则最终最短塔的最终高度为 min( h ₁  +  k ,  h _{i +1}  ?  k )，最终最高塔的最终高度为 max( h _i  +  k ,  h _n  ?  k )。在这种情况下，最后的区别是后者减去前者。
• 如果i  =  n，那么我们平等地增加了所有塔的高度，所以最终的差异只是h _n  ？ ħ ₁。

然后我们从所有最不差ñ这些可能性。

这是一个实现这一点的 Java 方法（假设为int-valued heights；注意h _i是arr[i-1]并且h _{i +1}是arr[i]）：

private static int doIt(final int[] arr, final int k) {
    java.util.Arrays.sort(arr);
    final int n = arr.length;
    int result = arr[n - 1] - arr[0];
    for (int i = 1; i < n; ++i) {
        final int min = Math.min(arr[0] + k, arr[i] - k);
        final int max = Math.max(arr[n - 1] - k, arr[i - 1] + k);
        result = Math.min(result, max - min);
    }
    return result;
}

请注意，为方便起见，我在循环之前拉了i  =  n案例。

Answer 2

假设您有三座塔，高度分别为 1、4 和 7，并且 k = 3。根据您的推理，最佳最小差值是 (7 - 3) - (1 + 3) = 0。但是您如何处理塔身高4？您需要增加或减少此值，因此在此示例中您可以实现的最小差异实际上是 3。

即使您被允许将塔保持在其高度，那么示例 1、5、7 也会反驳您的假设。

我知道这并不能解决实际的最小化问题，但它确实表明它并不像你想象的那么简单。我希望这能回答您的问题“我错过了什么吗？”。