最小化高度之间的最大差异
原文： 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 校园内）
想法是对所有元素按升序进行排序。 对于所有元素，请检查减法（element-k）和加法（element + k）是否进行任何更改。
下面是上述方法的实现：
C++
// 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 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
# 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#
// 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 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)。
版权属于：月萌API www.moonapi.com，转载请注明出处
