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

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

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

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

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

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

The big thing to observe is that for any given tower, if you choose to increase its height from h_i to h_i + k, then you might as well increase the height of all shorter towers: that won't affect the maximum (because if h_j < h_i, then h_j + k < h_i + k), and may help by increasing the minimum. Conversely, if you choose to decrease the height of a tower from h_i to h_i − k, then you might as well decrease the heights of all taller towers.

So while there are 2ⁿ possible ways to choose which towers should be increased vs. decreased, we can actually ignore most of these. Some tower will be the tallest tower that we increase the height of; for all shorter towers, we will increase their height as well, and for all taller towers, we will decrease their height. So there are only n interesting ways to choose which towers should be increased vs. decreased: one for each tower's chance to be the tallest tower that we increase the height of.

[迂腐的注释#1：您可能会注意到，降低高度也是有效的 all 塔，在这种情况下就没有这样的塔。但这相当于增加所有塔的高度——无论我们是否相加 k 到每个高度或减去 k 从各个高度来看，无论哪种方式，我们实际上都没有改变最大-最小。]

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

So, let's start by sorting the original heights and numbering them in increasing order, so that h₁ is the original height of the originally-shortest tower and h_n is the original height of the originally-tallest tower.

For each i, try the possibility that the ith-shortest tower is the tallest tower that we increase the height of; that is, try the possibility that we increase h₁ through h_i and decrease h_i+1 through h_n. There are two groups of cases:

• If i < n, then the final height of the finally-shortest tower is min(h₁ + k, h_i+1 − k), and the final height of the finally-tallest tower is max(h_i + k, h_n − k). The final difference in this case is the latter minus the former.
• If i = n, then we've increased the heights of all towers equally, so the final difference is just h_n − h₁.

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

Here's a Java method that implements this (assuming int-valued heights; note that h_i is arr[i-1] and h_i+1 is 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为了方便起见，在循环之前使用 case。