最小化高度之间的最大差异

Question

给定 n 个塔的高度和一个值 k。我们需要将每个塔的高度增加或减少 k（仅一次），其中 k > 0。任务是最小化修改后最长和最短塔的高度之间的差异，并输出该差异。

我得到了解决方案背后的直觉，但我无法评论下面解决方案的正确性。

// C++ program to find the minimum possible 
// difference between maximum and minimum 
// elements when we have to add/subtract 
// every number by k 
#include <bits/stdc++.h> 
using namespace std; 
  
// Modifies the array by subtracting/adding 
// k to every element such that the difference 
// between maximum and minimum is minimized 
int getMinDiff(int arr[], int n, int k) 
{ 
    if (n == 1) 
       return 0; 
  
    // Sort all elements 
    sort(arr, arr+n); 
  
    // Initialize result 
    int ans = arr[n-1] - arr[0]; 
  
    // Handle corner elements 
    int small = arr[0] + k; 
    int big = arr[n-1] - k; 
    if (small > big) 
       swap(small, big); 
  
    // Traverse middle elements 
    for (int i = 1; i < n-1; i ++) 
    { 
        int subtract = arr[i] - k; 
        int add = arr[i] + k; 
  
        // If both subtraction and addition 
        // do not change diff 
        if (subtract >= small || add <= big) 
            continue; 
  
        // Either subtraction causes a smaller 
        // number or addition causes a greater 
        // number. Update small or big using 
        // greedy approach (If big - subtract 
        // causes smaller diff, update small 
        // Else update big) 
        if (big - subtract <= add - small) 
            small = subtract; 
        else
            big = add; 
    } 
  
    return  min(ans, big - small); 
} 
  
// Driver function to test the above function 
int main() 
{ 
    int arr[] = {4, 6}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int k = 10; 
    cout << "\nMaximum difference is "
        << getMinDiff(arr, n, k); 
    return 0; 
} 

谁能帮我提供这个问题的正确解决方案？

Answer 1

上面的代码有效，但是我没有找到太多解释，所以我会尝试添加一些以帮助培养直觉。

对于任何给定的塔，如果您选择将其高度从H _i增加到H _i  +  K，那么您还可以增加所有较短塔的高度，因为这不会影响最大值。同样，如果您选择将塔的高度从H _{i 降低}到H _i  ？ K，那么您还可以降低所有较高塔的高度。
我们将利用这一点，我们有 n 座建筑物，我们将尝试使每座建筑物都最高，然后看看使哪座建筑物最高可以使我们的高度范围最小（这是我们的答案）。
让我解释：

所以我们想要做的是 -
1）我们首先对数组进行排序（你很快就会明白为什么）。

2）然后对于从 i = 0 到 n-2 ^{[1] 的}每个建筑物，我们尝试使其最高（通过向建筑物添加 K，向其左侧的建筑物添加 K 并从其右侧的建筑物中减去 K） .

因此，假设我们在建筑物H _i，我们已经将 K 加到它和它之前的建筑物中，并从它之后的建筑物中减去 K。

所以建筑物的最小高度现在将是min( H ₀  +  K , H _i+1  -  K )，
即 min(1st building + K, next building on right - K)。

（注意：这是因为我们对数组进行了排序。举几个例子说服自己。）

同样，建筑物的最大高度将为max( H _i  +  K , H _n-1  -  K )，
即 max(当前建筑物+ K，右边最后一栋建筑 - K)。

3) max - min 为您提供范围。

^[1]注意当 i = n-1 时。在这种情况下，当前建筑物之后没有建筑物，因此我们将 K 添加到每个建筑物中，因此范围仅为 height[n-1] - height[0] 因为 K 已添加到所有内容中，因此它取消出去。

这是基于上述想法的 Java 实现：

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;
    }
}

Answer 2

int getMinDiff(int a[], int n, int k) {
        sort(a,a+n); 
        int i,mx,mn,ans;
        ans = a[n-1]-a[0];  // this can be one possible solution
        
        for(i=0;i<n;i++)
        {
            if(a[i]>=k)  // since height of tower can't be -ve so taking only +ve heights
            {
                mn = min(a[0]+k, a[i]-k);
                mx = max(a[n-1]-k, a[i-1]+k);
                ans = min(ans, mx-mn);
            }
        }
        return ans;
    }

这是C++代码，它通过了所有测试用例。

Answer 3

这段Python代码可能对你有一些帮助。代码是不言自明的。

def getMinDiff(arr, n, k):
    arr = sorted(arr)
    ans = arr[-1]-arr[0] #this case occurs when either we subtract k or add k to all elements of the array
    for i in range(n):
        mn=min(arr[0]+k, arr[i]-k) #after sorting, arr[0] is minimum. so adding k pushes it towards maximum. We subtract k from arr[i] to get any other worse (smaller) minimum. worse means increasing the diff b/w mn and mx
        mx=max(arr[n-1]-k, arr[i]+k) # after sorting, arr[n-1] is maximum. so subtracting k pushes it towards minimum. We add k to arr[i] to get any other worse (bigger) maximum. worse means increasing the diff b/w mn and mx
        ans = min(ans, mx-mn)
    return ans