# 最小化高度之間的最大差異 > 原文： [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} ``` 來源： [Adob??e 面試體驗| 系列 24（MTS 校園內）](https://www.geeksforgeeks.org/adobe-interview-experience-set-24-on-campus-for-mts/) 想法是對所有元素按升序進行排序。 對于所有元素，請檢查減（element-k）和加（element + k）是否進行任何更改。 下面是上述方法的實現：  ## 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)`