Dada una array no decreciente arr[] y un entero K , la tarea es eliminar K elementos de la array de modo que la diferencia máxima entre los elementos adyacentes sea mínima.
Nota: K < N – 2
Ejemplos:
Entrada: arr[] = {3, 7, 8, 10, 14}, K = 2
Salida: 2
Explicación:
Después de eliminar los elementos A[0] y A[4],
la diferencia máxima entre elementos adyacentes es mínima.
Después de eliminar elementos, la array restante es [7, 8, 10]Entrada: arr[] = [12, 16, 22, 31, 31, 38], K = 3
Salida: 6
Explicación:
Después de eliminar los elementos A[3], A[4] y A[5],
la diferencia máxima entre elementos adyacentes es mínimo.
Después de eliminar elementos, la array restante es [12, 16, 22]
Método 1: Fuerza bruta La idea es generar subconjuntos de la array de tamaño N – K y también calcular la diferencia máxima de los elementos adyacentes en cada subsecuencia. Finalmente, encuentre el mínimo de dichas diferencias máximas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array #include <bits/stdc++.h> using namespace std; // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array int minimumAdjacentDifference(vector<int> a, int n, int k) { // Initialising the // minimum difference int minDiff = INT_MAX; // Traversing over subsets // in iterative manner for (int i = 0; i < (1 << n); i++) { // Number of elements to // be taken in the subset // ON bits of i represent // elements not to be removed int cnt = __builtin_popcount(i); // If the removed // set is of size k if (cnt == n - k) { // Creating the new array // after removing elements vector<int> temp; for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) temp.push_back(a[j]); } // Maximum difference of adjacent // elements of remaining array int maxDiff = INT_MIN; for (int j = 0; j < temp.size() - 1; j++) { maxDiff = max(maxDiff, temp[j + 1] - temp[j]); } minDiff = min(minDiff, maxDiff); } } return minDiff; } // Driver Code int main() { int n = 5; int k = 2; vector<int> a= { 3, 7, 8, 10, 14 }; cout << minimumAdjacentDifference(a, n, k); return 0; }
Java
// Java implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array import java.util.*; class GFG{ // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array static int minimumAdjacentDifference(int a[], int n, int k) { // Initialising the // minimum difference int minDiff = Integer.MAX_VALUE; // Traversing over subsets // in iterative manner for (int i = 0; i < (1 << n); i++) { // Number of elements to // be taken in the subset // ON bits of i represent // elements not to be removed int cnt = Integer.bitCount(i); // If the removed // set is of size k if (cnt == n - k) { // Creating the new array // after removing elements Vector<Integer> temp = new Vector<Integer>(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) temp.add(a[j]); } // Maximum difference of adjacent // elements of remaining array int maxDiff = Integer.MIN_VALUE; for (int j = 0; j < temp.size() - 1; j++) { maxDiff = Math.max(maxDiff, temp.get(j + 1) - temp.get(j)); } minDiff = Math.min(minDiff, maxDiff); } } return minDiff; } // Driver Code public static void main(String args[]) { int n = 5; int k = 2; int a[] = { 3, 7, 8, 10, 14 }; System.out.println(minimumAdjacentDifference(a, n, k)); } } // This code is contributed by AbhiThakur
Python3
# Python3 implementation to find the # minimum of the maximum difference # of the adjacent elements after # removing K elements from the array import sys INT_MAX = sys.maxsize; INT_MIN = -(sys.maxsize - 1) # Function to find the minimum # of the maximum difference of the # adjacent elements after removing # K elements from the array def minimumAdjacentDifference(a, n, k) : # Initialising the # minimum difference minDiff = INT_MAX; # Traversing over subsets # in iterative manner for i in range( 1<<n) : # Number of elements to # be taken in the subset # ON bits of i represent # elements not to be removed cnt = bin(i).count('1'); # If the removed # set is of size k if (cnt == n - k) : # Creating the new array # after removing elements temp = []; for j in range(n) : if ((i & (1 << j)) != 0) : temp.append(a[j]); # Maximum difference of adjacent # elements of remaining array maxDiff = INT_MIN; for j in range(len(temp) - 1) : maxDiff = max(maxDiff, temp[j + 1] - temp[j]); minDiff = min(minDiff, maxDiff); return minDiff; # Driver Code if __name__ == "__main__" : n = 5; k = 2; a = [ 3, 7, 8, 10, 14 ]; print(minimumAdjacentDifference(a, n, k)); # This code is contributed by AnkitRai01
C#
// C# implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array using System; using System.Collections.Generic; class GFG{ // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array static int minimumAdjacentDifference(int []a, int n, int k) { // Initialising the // minimum difference int minDiff = int.MaxValue; // Traversing over subsets // in iterative manner for (int i = 0; i < (1 << n); i++) { // Number of elements to // be taken in the subset // ON bits of i represent // elements not to be removed int cnt = countSetBits(i); // If the removed // set is of size k if (cnt == n - k) { // Creating the new array // after removing elements List<int> temp = new List<int>(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) temp.Add(a[j]); } // Maximum difference of adjacent // elements of remaining array int maxDiff = int.MinValue; for (int j = 0; j < temp.Count - 1; j++) { maxDiff = Math.Max(maxDiff, temp[j + 1] - temp[j]); } minDiff = Math.Min(minDiff, maxDiff); } } return minDiff; } static int countSetBits(int x) { int setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits; } // Driver Code public static void Main(String []args) { int n = 5; int k = 2; int []a = { 3, 7, 8, 10, 14 }; Console.WriteLine(minimumAdjacentDifference(a, n, k)); } } // This code is contributed by sapnasingh4991
Javascript
<script> // Javascript implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array function countSetBits(x) { let setBits = 0; while (x != 0) { x = x & (x - 1); setBits++; } return setBits; } // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array function minimumAdjacentDifference(a, n, k) { // Initialising the // minimum difference let minDiff = Number.MAX_VALUE; // Traversing over subsets // in iterative manner for(let i = 0; i < (1 << n); i++) { // Number of elements to // be taken in the subset // ON bits of i represent // elements not to be removed let cnt = countSetBits(i); // If the removed // set is of size k if (cnt == n - k) { // Creating the new array // after removing elements let temp = []; for(let j = 0; j < n; j++) { if ((i & (1 << j)) != 0) temp.push(a[j]); } // Maximum difference of adjacent // elements of remaining array let maxDiff = Number.MIN_VALUE; for(let j = 0; j < temp.length - 1; j++) { maxDiff = Math.max( maxDiff, temp[j + 1] - temp[j]); } minDiff = Math.min(minDiff, maxDiff); } } return minDiff; } // Driver code let n = 5; let k = 2; let a = [ 3, 7, 8, 10, 14 ]; document.write(minimumAdjacentDifference(a, n, k)); // This code is contributed by divyesh072019 </script>
2
Tiempo Complejidad: O(2 N * N)
Espacio auxiliar: O(N)
Método 2: Enfoque óptimo
- En una observación cuidadosa, se puede notar que, si la eliminación del elemento se realiza desde algún lugar entre la array (es decir, no los elementos finales), entonces la diferencia máxima de los elementos restantes solo puede aumentar o permanecer igual.
Por ejemplo:
Let the given array be {1, 5, 6}, If we remove the element 5(not the end element), then the maximum difference will always increase. Therefore, It is always better to remove end elements.
- Esto significa que el arreglo resultante después de eliminar K elementos será un subarreglo del arreglo original de tamaño N – K.
- Por lo tanto, podemos iterar sobre todos los subarreglos de tamaño N – K y para cada subarreglo encontrar la diferencia máxima entre elementos adyacentes. Finalmente, encuentre el mínimo de todas las diferencias máximas de los elementos adyacentes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array #include <bits/stdc++.h> using namespace std; // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array int minimumAdjacentDifference(vector<int> a, int n, int k) { // Initialising the // minimum difference int minDiff = INT_MAX; // Iterating over all // subarrays of size n-k for (int i = 0; i <= k; i++) { // Maximum difference after // removing elements int maxDiff = INT_MIN; for (int j = 0; j < n - k - 1; j++) { for (int p = i; p <= i + j; p++) { maxDiff = max(maxDiff, a[p + 1] - a[p]); } } // Minimum Adjacent Difference minDiff = min(minDiff, maxDiff); } return minDiff; } // Driver Code int main() { int n = 5; int k = 2; vector<int> a = { 3, 7, 8, 10, 14 }; cout << minimumAdjacentDifference(a, n, k); return 0; }
Java
// Java implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array class GFG { // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array static int minimumAdjacentDifference(int a[], int n, int k) { // Initialising the // minimum difference int minDiff = Integer.MAX_VALUE; // Iterating over all // subarrays of size n-k for (int i = 0; i <= k; i++) { // Maximum difference after // removing elements int maxDiff = Integer.MIN_VALUE; for (int j = 0; j < n - k - 1; j++) { for (int p = i; p <= i + j; p++) { maxDiff = Math.max(maxDiff, a[p + 1] - a[p]); } } // Minimum Adjacent Difference minDiff = Math.min(minDiff, maxDiff); } return minDiff; } // Driver Code public static void main (String[] args) { int n = 5; int k = 2; int []a = { 3, 7, 8, 10, 14 }; System.out.println(minimumAdjacentDifference(a, n, k)); } } // This code is contributed by Yash_R
Python3
# Python3 implementation to find the # minimum of the maximum difference # of the adjacent elements after # removing K elements from the array import sys INT_MAX = sys.maxsize; INT_MIN = -(sys.maxsize - 1); # Function to find the minimum # of the maximum difference of the # adjacent elements after removing # K elements from the array def minimumAdjacentDifference(a, n, k) : # Initialising the # minimum difference minDiff = INT_MAX; # Iterating over all # subarrays of size n-k for i in range(k + 1) : # Maximum difference after # removing elements maxDiff = INT_MIN; for j in range( n - k - 1) : for p in range(i, i + j + 1) : maxDiff = max(maxDiff, a[p + 1] - a[p]); # Minimum Adjacent Difference minDiff = min(minDiff, maxDiff); return minDiff; # Driver Code if __name__ == "__main__" : n = 5; k = 2; a = [ 3, 7, 8, 10, 14 ]; print(minimumAdjacentDifference(a, n, k)); # This code is contributed by AnkitRai01
C#
// C# implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array using System; class GFG { // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array static int minimumAdjacentDifference(int []a, int n, int k) { // Initialising the // minimum difference int minDiff = int.MaxValue; // Iterating over all // subarrays of size n-k for (int i = 0; i <= k; i++) { // Maximum difference after // removing elements int maxDiff = int.MinValue; for (int j = 0; j < n - k - 1; j++) { for (int p = i; p <= i + j; p++) { maxDiff = Math.Max(maxDiff, a[p + 1] - a[p]); } } // Minimum Adjacent Difference minDiff = Math.Min(minDiff, maxDiff); } return minDiff; } // Driver Code public static void Main (string[] args) { int n = 5; int k = 2; int []a = { 3, 7, 8, 10, 14 }; Console.WriteLine(minimumAdjacentDifference(a, n, k)); } } // This code is contributed by Yash_R
Javascript
<script> // JavaScript implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array function minimumAdjacentDifference(a,n,k) { // Initialising the // minimum difference let minDiff = Number.MAX_VALUE; // Iterating over all // subarrays of size n-k for (let i = 0; i <= k; i++) { // Maximum difference after // removing elements let maxDiff = Number.MIN_VALUE; for (let j = 0; j < n - k - 1; j++) { for (let p = i; p <= i + j; p++) { maxDiff = Math.max(maxDiff, a[p + 1] - a[p]); } } // Minimum Adjacent Difference minDiff = Math.min(minDiff, maxDiff); } return minDiff; } // Driver Code let n = 5; let k = 2; let a = [ 3, 7, 8, 10, 14 ]; document.write(minimumAdjacentDifference(a, n, k)); // This code is contributed by sravan </script>
2
Complejidad temporal: O(N * K 2 )
Espacio auxiliar: O(1)
Método 3: enfoque eficiente
- Usando la idea del Método 2, necesitamos encontrar el mínimo o el máximo de diferencias de elementos adyacentes de todos los subarreglos de tamaño N – K. Si creamos un arreglo de diferencias, es decir, un arreglo de diferencias de elementos adyacentes del arreglo inicial, entonces todo lo que lo que debe hacer es encontrar el elemento mínimo del máximo de todos los subarreglos de tamaño N – K – 1 de esta array de diferencia (ya que este máximo representará la diferencia adyacente máxima del subarreglo de tamaño N – K de la array original).
- Para realizar esta operación podemos usar el método de ventana deslizante usando la cola de dos extremos. Consulte Máximo de ventana deslizante (Máximo de todos los subarreglos de tamaño K) para este enfoque.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array #include <bits/stdc++.h> using namespace std; // Function to find the minimum // different in the subarrays // of size K in the array int findKMin(vector<int> arr, int n, int k) { // Create a Double Ended Queue, Qi // that will store indexes // of array elements, queue will // store indexes of useful elements // in every window deque<int> Qi(k); // Process first k (or first window) // elements of array int i; for (i = 0; i < k; ++i) { // For every element, // the previous smaller elements // are useless so remove them from Qi while ((!Qi.empty()) && arr[i] >= arr[Qi.back()]) Qi.pop_back(); // Remove from rear // Add new element at rear of queue Qi.push_back(i); } int minDiff = INT_MAX; // Process rest of the elements, // i.e., from arr[k] to arr[n-1] for (; i < n; ++i) { // The element at the front // of the queue is the largest // element of previous window minDiff = min(minDiff, arr[Qi.front()]); // Remove the elements // which are out of this window while ((!Qi.empty()) && Qi.front() <= i - k) Qi.pop_front(); // Remove all elements smaller // than the currently being // added element (remove useless elements) while ((!Qi.empty()) && arr[i] >= arr[Qi.back()]) Qi.pop_back(); // Add current element // at the rear of Qi Qi.push_back(i); } // compare the maximum // element of last window minDiff = min(minDiff, arr[Qi.front()]); return minDiff; } // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array int minimumAdjacentDifference(vector<int> a, int n, int k) { // Create the difference array vector<int> diff(n-1); for (int i = 0; i < n - 1; i++) { diff[i] = a[i + 1] - a[i]; } // find minimum of all maximum // of subarray sizes n - k - 1 int answer = findKMin(diff, n - 1, n - k - 1); return answer; } // Driver Code int main() { int n = 5; int k = 2; vector<int> a= { 3, 7, 8, 10, 14 }; cout << minimumAdjacentDifference(a, n, k); return 0; }
Java
// Java implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array import java.util.*; import java.lang.*; class GFG{ // Function to find the minimum // different in the subarrays // of size K in the array static int findKMin(int arr[], int n, int k) { // Create a Double Ended Queue, Qi // that will store indexes // of array elements, queue will // store indexes of useful elements // in every window Deque<Integer> Qi = new LinkedList<>(); // Process first k (or first window) // elements of array int i; for(i = 0; i < k; ++i) { // For every element, // the previous smaller elements // are useless so remove them from Qi while ((!Qi.isEmpty()) && arr[i] >= arr[Qi.peekLast()]) // Remove from rear Qi.pollLast(); // Add new element at rear of queue Qi.addLast(i); } int minDiff = Integer.MAX_VALUE; // Process rest of the elements, // i.e., from arr[k] to arr[n-1] for(; i < n; ++i) { // The element at the front // of the queue is the largest // element of previous window minDiff = Math.min(minDiff, arr[Qi.peekFirst()]); // Remove the elements // which are out of this window while ((!Qi.isEmpty()) && Qi.peekFirst() <= i - k) Qi.pollFirst(); // Remove all elements smaller // than the currently being // added element (remove useless elements) while ((!Qi.isEmpty()) && arr[i] >= arr[Qi.peekLast()]) Qi.pollLast(); // Add current element // at the rear of Qi Qi.addLast(i); } // Compare the maximum // element of last window minDiff = Math.min(minDiff, arr[Qi.peekFirst()]); return minDiff; } // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array static int minimumAdjacentDifference(int a[], int n, int k) { // Create the difference array int[] diff = new int[n - 1]; for(int i = 0; i < n - 1; i++) { diff[i] = a[i + 1] - a[i]; } // find minimum of all maximum // of subarray sizes n - k - 1 int answer = findKMin(diff, n - 1, n - k - 1); return answer; } // Driver code public static void main(String[] args) { int n = 5; int k = 2; int a[] = { 3, 7, 8, 10, 14 }; System.out.println(minimumAdjacentDifference(a, n, k)); } } // This code is contributed by offbeat
Python3
# Python3 implementation to find the # minimum of the maximum difference # of the adjacent elements after # removing K elements from the array import sys # Function to find the minimum # different in the subarrays # of size K in the array def findKMin(arr, n, k): # Create a Double Ended Queue, Qi # that will store indexes # of array elements, queue will # store indexes of useful elements # in every window Qi = [] # Process first k (or first window) # elements of array i = 0 for j in range(k): # For every element, # the previous smaller elements # are useless so remove them from Qi while ((len(Qi) != 0) and arr[i] >= arr[Qi[-1]]): Qi.pop() # Remove from rear # Add new element at rear of queue Qi.append(i) i += 1 minDiff = sys.maxsize; # Process rest of the elements, # i.e., from arr[k] to arr[n-1] for j in range(i, n): # The element at the front # of the queue is the largest # element of previous window minDiff = min(minDiff, arr[Qi[0]]) # Remove the elements # which are out of this window while ((len(Qi) != 0) and Qi[0] <= i - k): Qi.pop(0) # Remove all elements smaller # than the currently being # added element (remove # useless elements) while ((len(Qi) != 0) and arr[i] >= arr[Qi[-1]]): Qi.pop() # Add current element # at the rear of Qi Qi.append(i) i += 1 # Compare the maximum # element of last window minDiff = min(minDiff, arr[Qi[0]]) return minDiff # Function to find the minimum # of the maximum difference of the # adjacent elements after removing # K elements from the array def minimumAdjacentDifference(a, n, k): # Create the difference array diff = [0 for i in range(n - 1)] for i in range(n - 1): diff[i] = a[i + 1] - a[i] # Find minimum of all maximum # of subarray sizes n - k - 1 answer = findKMin(diff, n - 1, n - k - 1) return answer # Driver code if __name__=="__main__": n = 5 k = 2 a = [ 3, 7, 8, 10, 14 ] print(minimumAdjacentDifference(a, n, k)) # This code is contributed by rutvik_56
C#
// C# implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array using System; using System.Collections.Generic; class GFG { // Function to find the minimum // different in the subarrays // of size K in the array static int findKMin(List<int> arr, int n, int k) { // Create a Double Ended Queue, Qi // that will store indexes // of array elements, queue will // store indexes of useful elements // in every window List<int> Qi = new List<int>(); // Process first k (or first window) // elements of array int i = 0; for (int j = 0; j < k; j++) { // For every element, // the previous smaller elements // are useless so remove them from Qi while ((Qi.Count != 0) && (arr[i] >= arr[Qi[Qi.Count - 1]])) Qi.RemoveAt(Qi.Count - 1); // Remove from rear // Add new element at rear of queue Qi.Add(i); i += 1; } int minDiff = Int32.MaxValue; // Process rest of the elements, // i.e., from arr[k] to arr[n-1] for (int j = i; j < n; j++) { // The element at the front // of the queue is the largest // element of previous window minDiff = Math.Min(minDiff, arr[Qi[0]]); // Remove the elements // which are out of this window while ((Qi.Count != 0) && (Qi[0] <= i - k)) Qi.RemoveAt(0); // Remove all elements smaller // than the currently being // added element (remove // useless elements) while ((Qi.Count != 0) && (arr[i] >= arr[Qi[Qi.Count - 1]])) Qi.RemoveAt(Qi.Count - 1); // Add current element // at the rear of Qi Qi.Add(i); i += 1; } // Compare the maximum // element of last window minDiff = Math.Min(minDiff, arr[Qi[0]]); return minDiff; } // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array static int minimumAdjacentDifference(int[] a, int n, int k) { // Create the difference array List<int> diff = new List<int>(); for (var i = 0; i < n - 1; i++) diff.Add(a[i + 1] - a[i]); // Find minimum of all maximum // of subarray sizes n - k - 1 var answer = findKMin(diff, n - 1, n - k - 1); return answer; } // Driver code public static void Main(string[] args) { int n = 5; int k = 2; int[] a = { 3, 7, 8, 10, 14 }; // Function call Console.Write(minimumAdjacentDifference(a, n, k)); } } // This code is contributed by phasing17
Javascript
<script> // JavaScript implementation to find the // minimum of the maximum difference // of the adjacent elements after // removing K elements from the array // Function to find the minimum // different in the subarrays // of size K in the array function findKMin(arr, n, k) { // Create a Double Ended Queue, Qi // that will store indexes // of array elements, queue will // store indexes of useful elements // in every window var Qi = []; // Process first k (or first window) // elements of array var i = 0; for (var j = 0; j < k; j++) { // For every element, // the previous smaller elements // are useless so remove them from Qi while ((Qi.length != 0) && (arr[i] >= arr[Qi[-1]])) Qi.pop(); // Remove from rear // Add new element at rear of queue Qi.push(i); i += 1; } var minDiff = Number.MAX_SAFE_INTEGER; // Process rest of the elements, // i.e., from arr[k] to arr[n-1] for (var j = i; j < n; j++) { // The element at the front // of the queue is the largest // element of previous window minDiff = Math.min(minDiff, arr[Qi[0]]); // Remove the elements // which are out of this window while ((Qi.length != 0) && (Qi[0] <= i - k)) Qi.shift(); // Remove all elements smaller // than the currently being // added element (remove // useless elements) while ((Qi.length != 0) && (arr[i] >= arr[Qi[Qi.length -1]])) Qi.pop(); // Add current element // at the rear of Qi Qi.push(i); i += 1; } // Compare the maximum // element of last window minDiff = Math.min(minDiff, arr[Qi[0]]); return minDiff; } // Function to find the minimum // of the maximum difference of the // adjacent elements after removing // K elements from the array function minimumAdjacentDifference(a, n, k) { // Create the difference array var diff = []; for (var i = 0; i < n - 1; i++) diff.push(a[i + 1] - a[i]); // Find minimum of all maximum // of subarray sizes n - k - 1 var answer = findKMin(diff, n - 1, n - k - 1); return answer; } // Driver code let n = 5; let k = 2; let a = [ 3, 7, 8, 10, 14 ]; // function call document.write(minimumAdjacentDifference(a, n, k)); // This code is contributed by phasing17 </script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)