Minimizar la diferencia máxima entre las alturas

Dadas las alturas de N torres y un valor de K , aumente o disminuya la altura de cada torre en K (solo una vez) donde K > 0. Después de las modificaciones, la tarea es minimizar la diferencia entre las alturas de la más larga y la más alta. torre más corta y generar esta diferencia.

Ejemplos: 

Entrada: arr[] = {1, 15, 10}, k = 6
Salida:   La diferencia máxima es 5.
Explicación: Cambie 1 a 7, 15 a 9 y 10 a 4. La diferencia máxima es 5 (entre 4 y 9). No podemos obtener una diferencia más baja.

Entrada: arr[] = {1, 5, 15, 10}, k = 3   
Salida: la diferencia máxima es 8, arr[] = {4, 8, 12, 7}

Fuente: experiencia de entrevista de Adobe | Conjunto 24 (en el campus para MTS)

Acercarse:

Ordene la array e intente hacer que cada altura de la torre sea máxima disminuyendo la altura de todas las torres a la derecha en k y aumentando todas las alturas de las torres a la izquierda en k. Compruebe si la torre de índice actual tiene la altura máxima o no comparándola con a[n]-k . Si la altura de la torre es mayor que la de a[n]-k , entonces es la torre más alta disponible.

Del mismo modo, encuentre la torre más corta y minimice la diferencia entre estas dos torres.  

Nota : Considere donde a[i] < K porque la altura de la torre no puede ser negativa, así que ignore ese caso.

A continuación se muestra la implementación del enfoque anterior:

// C++ Code for the Approach
 
#include <bits/stdc++.h>
using namespace std;
 
// User function Template
int getMinDiff(int arr[], int n, int k)
{
    sort(arr, arr + n);
   
      // Maximum possible height difference
    int ans = arr[n - 1] - arr[0];
 
    int tempmin, tempmax;
    tempmin = arr[0];
    tempmax = arr[n - 1];
 
    for (int i = 1; i < n; i++) {
       
          // If on subtracting k we got
          // negative then continue
        if(arr[i] - k < 0) continue;
         
          // Minimum element when we
          // add k to whole array
        tempmin= min(arr[0] + k,arr[i] - k);
         
          // Maximum element when we
          // subtract k from whole array
        tempmax = max(arr[i - 1] + k, arr[n - 1] - k);
                                                          
        ans = min(ans, tempmax - tempmin);
    }
    return ans;
}
 
// Driver Code Starts
int main()
{
   
    int k = 6, n = 6;
    int arr[n] = { 7, 4, 8, 8, 8, 9 };
   
      // Function Call
    int ans = getMinDiff(arr, n, k);
    cout << ans;
   
}

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
 
// Driver code
public class Main {
 
    public static void main(String[] args)
    {
        int[] arr = { 7, 4, 8, 8, 8, 9 };
        int k = 6;
        int ans = getMinDiff(arr, arr.length, k);
        System.out.println(ans);
    }
 
    // User function Template for Java
    public static int getMinDiff(int[] arr, int n, int k)
    {
 
        Arrays.sort(arr);
        // Maximum possible height difference
        int ans = arr[n - 1] - arr[0];
 
        int tempmin, tempmax;
        tempmin = arr[0];
        tempmax = arr[n - 1];
 
        for (int i = 1; i < n; i++) {
 
            // if on subtracting k we got negative then
            // continue
            if (arr[i] - k < 0)
                continue;
 
            // Minimum element when we add k to whole array
            tempmin = Math.min(arr[0] + k, arr[i] - k);
 
            // Maximum element when we subtract k from whole
            // array
            tempmax
                = Math.max(arr[i - 1] + k, arr[n - 1] - k);
            ans = Math.min(ans, tempmax - tempmin);
        }
        return ans;
    }
}

# User function Template
def getMinDiff(arr, n, k):
    arr.sort()
    ans = arr[n - 1] - arr[0]  # Maximum possible height difference
 
    tempmin = arr[0]
    tempmax = arr[n - 1]
 
    for i in range(1, n):
      if arr[i]<k:continue
      tempmin = min(arr[0] + k, arr[i] - k)
         
      # Minimum element when we
      # add k to whole array
      # Maximum element when we
      tempmax = max(arr[i - 1] + k, arr[n - 1] - k)
         
      # subtract k from whole array
      ans = min(ans, tempmax - tempmin)
 
    return ans
 
# Driver Code Starts
k = 6
n = 6
arr = [7, 4, 8, 8, 8, 9]
ans = getMinDiff(arr, n, k)
print(ans)
 
# This code is contributed by ninja_hattori.

using System;
 
public class GFG {
 
  static public int getMinDiff(int[] arr, int n, int k)
  {
 
    Array.Sort(arr);
    int ans
      = (arr[n - 1] + k)
      - (arr[0]
         + k); // Maximum possible height difference
 
    int tempmax
      = arr[n - 1] - k; // Maximum element when we
    // subtract k from whole array
    int tempmin = arr[0] + k; // Minimum element when we
    // add k to whole array
    int max, min;
 
    for (int i = 0; i < n - 1; i++) {
      if (tempmax > (arr[i] + k)) {
        max = tempmax;
      }
      else {
        max = arr[i] + k;
      }
 
      if (tempmin < (arr[i + 1] - k)) {
        min = tempmin;
      }
      else {
        min = arr[i + 1] - k;
      }
 
      if (ans > (max - min)) {
        ans = max - min;
      }
    }
    return ans;
  }
 
  static public void Main()
  {
    int[] arr = { 7, 4, 8, 8, 8, 9 };
    int k = 6;
    int ans = getMinDiff(arr, arr.Length, k);
    Console.Write(ans);
  }
}
 
// This code is contributed by ninja_hattori.

<script>
 
// User function Template
function getMinDiff(arr,n,k)
{
    arr.sort((a,b) => (a-b))
    let ans = arr[n - 1] - arr[0]; // Maximum possible height difference
 
    let tempmin, tempmax;
    tempmin = arr[0];
    tempmax = arr[n - 1];
 
    for (let i = 1; i < n; i++) {
        tempmin= Math.min(arr[0] + k,arr[i] - k); // Minimum element when we
                                                // add k to whole array
        tempmax = Math.max(arr[i - 1] + k, arr[n - 1] - k); // Maximum element when we
                                                         // subtract k from whole array
        ans = Math.min(ans, tempmax - tempmin);
    }
    return ans;
}
 
// Driver Code Starts
let k = 6, n = 6;
let arr = [ 7, 4, 8, 8, 8, 9 ];
let ans = getMinDiff(arr, n, k);
document.write(ans,"</br>");
 
//This code is contributed by shinjanpatra.
</script>

5

Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)