arrays - 塔高之间的最小差异？

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_i 到h_i − k，那么您不妨降低所有更高塔的高度。

因此虽然有 2ⁿ 种可能的方法来选择应该增加还是减少哪些塔，但我们实际上可以忽略其中的大部分。一些塔将是我们增加高度的最高塔；对于所有较矮的塔，我们也会增加它们的高度，而对于所有较高的塔，我们会降低它们的高度。所以只有 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 − h₁。

然后我们从所有 n 个可能性中取最小的差异。

这是一个实现此方法的 Java 方法(假设 int 值的高度；请注意 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 的情况。