c++ - 最小化高度之间的最大差异

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

上面的代码有效，但是我没有找到太多解释，所以我会尝试添加一些以帮助培养直觉。
对于任何给定的塔，如果您选择将其高度从 Hi 增加到 Hi + K，那么您还可以增加所有较短塔的高度，因为这不会影响最大值。同样，如果您选择将塔的高度从 Hi 降低到 Hi - K，那么您也可以降低所有较高塔的高度。
我们将利用这一点，我们有 n 座建筑物，我们将尝试使每座建筑物都最高，然后看看使哪座建筑物最高可以使我们的高度范围最小(这是我们的答案)。让我解释:
所以我们想要做的是 - 1)我们首先对数组进行排序(你很快就会明白为什么)。
2)然后对于从 i = 0 到 n-2[1] 的每个建筑物，我们尝试使其最高(通过向建筑物添加 K，向其左侧的建筑物添加 K 并从其右侧的建筑物中减去 K) .
因此，假设我们正在 build Hi，我们将 K 加到它和它之前的建筑物中，并从它后面的建筑物中减去 K。所以建筑物的最小高度现在是 min(H0 + K, Hi+1 - K)，即分钟(第一栋建筑 + K，右边的下一栋建筑 - K) .
(注意:这是因为我们对数组进行了排序。举几个例子来说服自己。)
同样，建筑物的最大高度将为 max(Hi + K, Hn-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;
    }
}