最小化高度之间的最大差异 · GeeksForGeeks 中文系列教程

# 最小化高度之间的最大差异 > 原文： [https://www.geeksforgeeks.org/minimize-the-maximum-difference-between-the-heights/](https://www.geeksforgeeks.org/minimize-the-maximum-difference-between-the-heights/) 给定 n 个塔的高度和值 k。我们需要将每个塔的高度增加或减少 k（仅一次），其中 k >0。任务是最小化修改后最长和最短塔的高度之间的差异，并输出该差异。 **示例**： ``` Input : arr[] = {1, 15, 10}, k = 6 Output : Maximum difference is 5. Explanation : We change 1 to 6, 15 to 9 and 10 to 4\. Maximum difference is 5 (between 4 and 9). We can't get a lower difference. Input : arr[] = {1, 5, 15, 10} k = 3 Output : Maximum difference is 8 arr[] = {4, 8, 12, 7} Input : arr[] = {4, 6} k = 10 Output : Maximum difference is 2 arr[] = {14, 16} OR {-6, -4} Input : arr[] = {6, 10} k = 3 Output : Maximum difference is 2 arr[] = {9, 7} Input : arr[] = {1, 10, 14, 14, 14, 15} k = 6 Output: Maximum difference is 5 arr[] = {7, 4, 8, 8, 8, 9} Input : arr[] = {1, 2, 3} k = 2 Output: Maximum difference is 2 arr[] = {3, 4, 5} ``` 来源： [Adobe 面试体验| 系列 24（MTS 校园内）](https://www.geeksforgeeks.org/adobe-interview-experience-set-24-on-campus-for-mts/) 想法是对所有元素按升序进行排序。对于所有元素，请检查减（element-k）和加（element + k）是否进行任何更改。下面是上述方法的实现： ![](https://img.kancloud.cn/c7/55/c755721aa04395d676a343d312bf2c54_1161x913.png) ## C++ ```cpp // 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; } ``` ## Java ```java // Java program to find the minimum possible // difference between maximum and minimum // elements when we have to add/subtract // every number by k import java.util.*; class GFG { // Modifies the array by subtracting/adding // k to every element such that the difference // between maximum and minimum is minimized static int getMinDiff(int arr[], int n, int k) { if (n == 1) return 0; // Sort all elements Arrays.sort(arr); // Initialize result int ans = arr[n-1] - arr[0]; // Handle corner elements int small = arr[0] + k; int big = arr[n-1] - k; int temp = 0; if (small > big) { temp = small; small = big; big = temp; } // 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 Math.min(ans, big - small); } // Driver function to test the above function public static void main(String[] args) { int arr[] = {4, 6}; int n = arr.length; int k = 10; System.out.println("Maximum difference is "+ getMinDiff(arr, n, k)); } } // This code is contributed by Prerna Saini ``` ## Python3 ```py # Python 3 program to find the minimum # possible difference between maximum # and minimum elements when we have to # add / subtract every number by k # Modifies the array by subtracting / # adding k to every element such that # the difference between maximum and # minimum is minimized def getMinDiff(arr, n, k): if (n == 1): return 0 # Sort all elements arr.sort() # Initialize result ans = arr[n-1] - arr[0] # Handle corner elements small = arr[0] + k big = arr[n-1] - k if (small > big): small, big = big, small # Traverse middle elements for i in range(1, n-1): subtract = arr[i] - k add = arr[i] + k # If both subtraction and addition # do not change diff if (subtract >= small or 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 arr = [ 4, 6 ] n = len(arr) k = 10 print("Maximum difference is", getMinDiff(arr, n, k)) # This code is contributed by # Smitha Dinesh Semwal ``` ## C# ```cs // C# program to find the minimum // possible difference between // maximum and minimum elements // when we have to add/subtract // every number by k using System; class GFG { // Modifies the array by subtracting/adding // k to every element such that the difference // between maximum and minimum is minimized static int getMinDiff(int[] arr, int n, int k) { if (n == 1) return 0; // Sort all elements Array.Sort(arr); // Initialize result int ans = arr[n - 1] - arr[0]; // Handle corner elements int small = arr[0] + k; int big = arr[n - 1] - k; int temp = 0; if (small > big) { temp = small; small = big; big = temp; } // 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 Math.Min(ans, big - small); } // Driver Code public static void Main() { int[] arr = {4, 6}; int n = arr.Length; int k = 10; Console.Write("Maximum difference is "+ getMinDiff(arr, n, k)); } } // This code is contributed // by ChitraNayal ``` ## PHP ```php <?php // PHP program to find the minimum // possible difference between // maximum and minimum elements when // we have to add/subtract every // number by k // Modifies the array by subtracting // or adding k to every element such // that the difference between maximum // and minimum is minimized function getMinDiff($arr, $n, $k) { if ($n == 1) return 0; // Sort all elements sort($arr); // Initialize result $ans = $arr[$n - 1] - $arr[0]; // Handle corner elements $small = $arr[0] + $k; $big = $arr[$n - 1] - $k; if ($small > $big) { $temp = $small; $small = $big; $big = $temp; } // Traverse middle elements for ($i = 1; $i < $n - 1; $i ++) { $subtract = $arr[$i] - $k; $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 Code $arr = array(4, 6); $n = sizeof($arr); $k = 10; echo "Maximum difference is "; echo getMinDiff($arr, $n, $k); // This code is contributed by ihritik ?> ``` **输出**： ``` Maximum difference is 2 ``` **时间复杂度**：`O(N log N)`