>我正在经历一些面试问题，我看到了这个
给定 n 个塔的高度和值 k。您必须将每座塔的高度增加或减少 k。您需要最小化最长和最短塔的高度差并输出此差值。
我认为答案将是(maxheight-k) - (minheight + k).我已经尝试了一些测试用例，它运行良好。
但我不确定，我想我错过了什么，是吗？
m7thon 的回答解释了您的解决方案的问题，所以我将只解释您如何实际解决这个问题......
要观察的重要事情是，对于任何给定的塔，如果您选择将其高度从h i 增加到h i + k，那么您也可以增加所有较短塔的高度：这不会影响最大值(因为如果h j
因此，虽然有 2n 种可能的方法可以选择增加和减少哪些塔，但我们实际上可以忽略其中的大部分。有些塔将成为我们增加高度的最高塔;对于所有较短的塔，我们也会增加它们的高度，对于所有较高的塔，我们将降低它们的高度。因此，只有n种有趣的方法可以选择增加和减少哪些塔：每个塔成为我们增加高度的最高塔的机会。
[迂腐的注释#1：你可能会注意到，降低所有塔的高度也是有效的，在这种情况下，没有这样的塔。但这相当于增加所有塔的高度——无论我们在每个高度上加 k 还是从每个高度中减去 k，无论哪种方式，我们实际上都没有改变最大-负-最小值。
[迂腐的注释#2：我只提到了"较短的塔"和"较高的塔"，但也有可能多个塔具有相同的初始高度。但这种情况并不重要，因为我们不妨全部增加或减少它们——增加一些而减少另一些是没有意义的。因此，此处描述的方法仍然有效。
因此，让我们首先对原始高度进行排序并按递增顺序对其进行编号，以便 h 1 是原始最短塔的原始高度，hn 是原始最高塔的原始高度。
对于每个 i，尝试第 i 个最短的塔是我们增加高度的最高塔的可能性;也就是说，尝试我们增加 h 1 到 h i 和减少 h i+1 到 hn 的可能性。有两组情况：
- 如果 i <n，那么最后最短的塔的最终高度是>
- i+1 − k(，最后最高的塔的最终高度是 max(h i + k， hn− k(。 在这种情况下，最后一个区别是后者减去前者。
- 如果 i = n，那么我们平均增加了所有塔的高度，所以最终的差值只是 h n − h1。
然后，我们从所有这些可能性中取最小的差异。
下面是一个实现这一点的 Java 方法(假设 int 值高度;请注意，h i 是 arr[i-1]，hi+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 的情况。
假设你有三座塔，高度分别为 1、4 和 7，k = 3。根据您的推理，最佳最小差值为 (7 - 3( - (1 + 3( = 0。但是你如何处理高度为 4 的塔？您需要增加或减少此值，因此在此示例中，您可以实现的最小差异实际上是 3。
即使允许你保持塔的高度，例子1、5、7也会反驳你的假设。
我知道这并不能解决实际的最小化问题，但它确实表明它并不像你想象的那么简单。我希望这能回答你的问题"我错过了什么吗？
我认为这来自gfg。
@ruakh的答案可能是我在网上找到的最好的答案，它适用于大多数情况，但对于 gfg 上的练习题，有少数情况会导致最小值低于 0，并且该问题不允许任何高度<0。
因此，为此，您需要进行额外的检查，其余部分几乎完全受ruakh的回答的启发
。class Solution {
int getMinDiff(int[] arr, int n, int k) {
Arrays.sort(arr);
int ans = arr[n-1] - arr[0];
int smallest = arr[0] + k, largest = arr[n-1]-k;
for(int i = 0; i < n-1; i++){
int min = Math.min(smallest, arr[i+1]-k);
int max = Math.max(largest, arr[i]+k);
if(min < 0) continue;
ans = Math.min(ans, max-min);
}
return ans;
}
}
我还对高度进行了基于 0 的索引，以使其更加明显，但也许这是主观的。
编辑：<0 检查很重要的一种情况是当数组 8 1 5 4 7 5 7 9 4 6 和 k 是 5。对此的预期答案是 8，如果没有 <0 检查，你会得到 7。
这里有点晚了。这些家伙已经向你解释了问题并给了你解决方案。但是，我自己准备了此代码。我准备的代码不是您应该遵循的最佳代码，但可以清楚地了解使用蛮力可以做些什么来实现这一点。
set = list(map(int, input().split()))
k = int(input())
min = 999999999
for index in range(2**len(set)):
binary = [] //probably should have used integer to binary fuction here
while index != 0:
remainder = index % 2
index //= 2
binary.append(remainder)
while len(binary) != len(set):
binary.append(0)
binary.reverse()
separateset = []
flag = 0
for i in range(len(binary)):
if binary[i] == 0:
separateset.append(set[i]+k)
elif binary[i] == 1 and set[i]-k >= 0:
separateset.append(set[i]-k)
else:
flag = 1
break
if flag == 0:
separateset.sort()
if min > separateset[-1] - separateset[0]:
min = separateset[-1] - separateset[0]
print(min)
这是通过识别set变量的所有可能子集来实现的，但只需进行一些修改。如果数字为 0，则set中该i的值(索引不是 for 循环中的index(与 k 否则，如果数字为 1 且set[i]-k >= 0，则set中该索引处的值减去 k(现在您可以加减k反之亦然， 在你得到+k和-k的所有可能组合之前，这并不重要(。 set[i]-k >= 0是要遵循的，因为负高度没有意义，如果发生这种情况，flag变为 1 并中断。但是，如果标志为 0，则表示所有高度均为正数，然后对separatesort进行排序，然后min存储最大和最短塔之间的差异。此min最终具有所有差异中的最小值。
步骤 1 ：
将所有高度减少"k"并按非降序排序。
步骤 2 ：
我们需要将一些高度子集增加 '2 * k'(因为它们减少了步骤1中的"k"，因此，为了有效地通过"k"增加它们的高度，我们需要以添加"2*k"(。
第 3 步 ：
显然，如果我们增加"i"高度而不增加'i-1'th那么，它将没有用，因为最小值仍然相同和最大值也可能增加！
第 4 步 ：
考虑所有前缀，并将"2*k"添加到前缀的每个元素中。然后计算并更新(最大值 - 最小值(值。
让我知道我在这里错过了哪个场景，
class Solution:
def getMinDiff(self, arr, n, k):
for i in range(n):
if arr[i] < k: arr[i] += k
else: arr[i] -= k
result = max(arr) - min(arr)
print('NewArr: {}nresult: {}'.format(arr, result))
return result
C++代码：
int getMinDiff(int arr[], int n, int k) {
// code here
sort(arr , arr+n);
int result = arr[n - 1] - arr[0];
for (int i = 1; i < n; ++i) {
int min_ = min(arr[0] + k, arr[i] - k);
int max_ = max(arr[n - 1] - k, arr[i - 1] + k);
result = min(result, max_ - min_);
}
return result;
}
首先，您需要找到塔的平均高度。假设高度是 3、7、17、25、45 和 k = 5平均值为 = ( 3 + 7 + 17 + 25 + 45 (/5 = 97/5 = 19.4
现在，我们将尝试使每栋建筑更接近平均高度。
对于 3 高度的塔，我们必须将 5 加 3 倍，使高度 = 3 + (3*5( = 18(18 更接近 23(接近平均值。
对于 7 高度，我们将加 5 两次 = 7 + (2 *5( = 17(17 比 22 更接近(
同样，25将变为 25 - 5 = 2045 将变为 45 - (5 *5( = 20
你的身高将变成18、17、17、20、20
这种方法适用于 GfG 实践，问题链接：https://practice.geeksforgeeks.org/problems/minimize-the-heights/0/
方法：
- 从数组中查找最大、最小元素。O(n(。取平均值，avg = (max_element + min_element(/2。
- 再次遍历数组，对于每个元素，检查它是否小于 avg 或更大。
- 如果当前元素 arr[i] 小于 avg，则将 "k" 添加到 a[i]，即 a[i] = a[i] + k。
- 如果当前元素 arr[i] 大于或等于 avg，则从 a[i] 中减去 k，即 a[i] = a[i] - k;
- 从修改后的数组中再次找出最小和最大元素。
- 返回 min(max1-min1， max2-min2(，其中 (max1， min1( = 数组修改前的 max 和 min 元素，(max2， min2( 是修改后的 max 和 min 元素。
完整的代码可以在这里找到：https://ide.geeksforgeeks.org/56qHOM0EOA