Dada una array arr[] que consta de N enteros y un entero K , la tarea es encontrar la diferencia mínima entre el elemento máximo y mínimo presente en la array después de eliminar cualquier subarreglo de tamaño K .
Ejemplos:
Entrada: arr[] = {4, 5, 8, 9, 1, 2}, K = 2
Salida: 4
Explicación: Elimina el subarreglo {8, 9}. La diferencia mínima entre los elementos de array máximos y mínimos se convierte en (5 – 1) = 4.Entrada: arr[] = {1, 2, 2}, K = 1
Salida: 0
Explicación: Elimina el subarreglo {1}. La diferencia mínima entre los elementos de array máximos y mínimos se convierte en (2 – 2) = 0.
Enfoque ingenuo: el enfoque más simple es eliminar todos los subarreglos posibles de tamaño K uno por uno y calcular la diferencia entre el máximo y el mínimo entre los elementos restantes. Finalmente, imprima la diferencia mínima obtenida.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar almacenando prefijos máximos y mínimos hasta cualquier índice y almacenando los máximos y mínimos suficientes a partir de cualquier índice. Una vez que se calculan los cuatro valores anteriores , encuentre los elementos de array máximos y mínimos después de eliminar un subarreglo de longitud K en una complejidad computacional constante.
Siga los pasos a continuación para resolver el problema:
- Inicialice las arrays maxSufix[] y minSuffix[] . tal que el i -ésimo elemento de la array maxSuffix[] y minSuffix[] denota los elementos máximo y mínimo respectivamente presentes a la derecha del i -ésimo índice.
- Inicialice dos variables, digamos maxPrefix y minPrefix, para almacenar los elementos máximo y mínimo presentes en el subarreglo de prefijos.
- Recorra la array sobre los índices [1, N] y verifique si i + K <= N o no. Si se encuentra que es cierto, entonces realice los siguientes pasos:
- El valor máximo presente en el arreglo después de eliminar un subarreglo de tamaño K a partir del i -ésimo índice es max(maxSuffix[i + k], maxPrefix).
- El valor mínimo presente en el arreglo después de eliminar un subarreglo de tamaño K a partir del i -ésimo índice es min(minSuffix[i + k], minPrefix).
- Actualice minDiff a min(minDiff, máximo – mínimo) para almacenar la diferencia mínima.
- Imprima minDiff como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to minimize difference
// between maximum and minimum array
// elements by removing a K-length subarray
void minimiseDifference(vector<int>& arr, int K)
{
// Size of array
int N = arr.size();
// Stores the maximum and minimum
// in the suffix subarray [i .. N-1]
int maxSuffix[N + 1], minSuffix[N + 1];
maxSuffix[N] = -1e9;
minSuffix[N] = 1e9;
maxSuffix[N - 1] = arr[N - 1];
minSuffix[N - 1] = arr[N - 1];
// Constructing the maxSuffix and
// minSuffix arrays
// Traverse the array
for (int i = N - 2; i >= 0; --i) {
maxSuffix[i] = max(
maxSuffix[i + 1],
arr[i]);
minSuffix[i] = min(
minSuffix[i + 1],
arr[i]);
}
// Stores the maximum and minimum
// in the prefix subarray [0 .. i-1]
int maxPrefix = arr[0];
int minPrefix = arr[0];
// Store the minimum difference
int minDiff = maxSuffix[K] - minSuffix[K];
// Traverse the array
for (int i = 1; i < N; ++i) {
// If the suffix doesn't exceed
// the end of the array
if (i + K <= N) {
// Store the maximum element
// in array after removing
// subarray of size K
int maximum = max(maxSuffix[i + K], maxPrefix);
// Stores the maximum element
// in array after removing
// subarray of size K
int minimum = min(minSuffix[i + K], minPrefix);
// Update minimum difference
minDiff = min(minDiff, maximum - minimum);
}
// Updating the maxPrefix and
// minPrefix with current element
maxPrefix = max(maxPrefix, arr[i]);
minPrefix = min(minPrefix, arr[i]);
}
// Print the minimum difference
cout << minDiff << "\n";
}
// Driver Code
int main()
{
vector<int> arr = { 4, 5, 8, 9, 1, 2 };
int K = 2;
minimiseDifference(arr, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to minimize difference
// between maximum and minimum array
// elements by removing a K-length subarray
static void minimiseDifference(int[] arr, int K)
{
// Size of array
int N = arr.length;
// Stores the maximum and minimum
// in the suffix subarray [i .. N-1]
int[] maxSuffix = new int[N + 1];
int[] minSuffix = new int[N + 1];
maxSuffix[N] = -1000000000;
minSuffix[N] = 1000000000;
maxSuffix[N - 1] = arr[N - 1];
minSuffix[N - 1] = arr[N - 1];
// Constructing the maxSuffix and
// minSuffix arrays
// Traverse the array
for (int i = N - 2; i >= 0; --i) {
maxSuffix[i]
= Math.max(maxSuffix[i + 1], arr[i]);
minSuffix[i]
= Math.min(minSuffix[i + 1], arr[i]);
}
// Stores the maximum and minimum
// in the prefix subarray [0 .. i-1]
int maxPrefix = arr[0];
int minPrefix = arr[0];
// Store the minimum difference
int minDiff = maxSuffix[K] - minSuffix[K];
// Traverse the array
for (int i = 1; i < N; ++i) {
// If the suffix doesn't exceed
// the end of the array
if (i + K <= N) {
// Store the maximum element
// in array after removing
// subarray of size K
int maximum
= Math.max(maxSuffix[i + K], maxPrefix);
// Stores the maximum element
// in array after removing
// subarray of size K
int minimum
= Math.min(minSuffix[i + K], minPrefix);
// Update minimum difference
minDiff
= Math.min(minDiff, maximum - minimum);
}
// Updating the maxPrefix and
// minPrefix with current element
maxPrefix = Math.max(maxPrefix, arr[i]);
minPrefix = Math.min(minPrefix, arr[i]);
}
// Print the minimum difference
System.out.print(minDiff);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 4, 5, 8, 9, 1, 2 };
int K = 2;
minimiseDifference(arr, K);
}
}
// This code is contributed by susmitakundugoaldanga.
Python3
# Python 3 program for the above approach # Function to minimize difference # between maximum and minimum array # elements by removing a K-length subarray def minimiseDifference(arr, K): # Size of array N = len(arr) # Stores the maximum and minimum # in the suffix subarray [i .. N-1] maxSuffix = [0 for i in range(N + 1)] minSuffix = [0 for i in range(N + 1)] maxSuffix[N] = -1e9 minSuffix[N] = 1e9 maxSuffix[N - 1] = arr[N - 1] minSuffix[N - 1] = arr[N - 1] # Constructing the maxSuffix and # minSuffix arrays # Traverse the array i = N - 2 while(i >= 0): maxSuffix[i] = max(maxSuffix[i + 1],arr[i]) minSuffix[i] = min(minSuffix[i + 1], arr[i]) i -= 1 # Stores the maximum and minimum # in the prefix subarray [0 .. i-1] maxPrefix = arr[0] minPrefix = arr[0] # Store the minimum difference minDiff = maxSuffix[K] - minSuffix[K] # Traverse the array for i in range(1, N): # If the suffix doesn't exceed # the end of the array if (i + K <= N): # Store the maximum element # in array after removing # subarray of size K maximum = max(maxSuffix[i + K], maxPrefix) # Stores the maximum element # in array after removing # subarray of size K minimum = min(minSuffix[i + K], minPrefix) # Update minimum difference minDiff = min(minDiff, maximum - minimum) # Updating the maxPrefix and # minPrefix with current element maxPrefix = max(maxPrefix, arr[i]) minPrefix = min(minPrefix, arr[i]) # Print the minimum difference print(minDiff) # Driver Code if __name__ == '__main__': arr = [4, 5, 8, 9, 1, 2] K = 2 minimiseDifference(arr, K) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFg {
// Function to minimize difference
// between maximum and minimum array
// elements by removing a K-length subarray
static void minimiseDifference(List<int> arr, int K)
{
// Size of array
int N = arr.Count;
// Stores the maximum and minimum
// in the suffix subarray [i .. N-1]
int[] maxSuffix = new int[N + 1];
int[] minSuffix = new int[N + 1];
maxSuffix[N] = -1000000000;
minSuffix[N] = 1000000000;
maxSuffix[N - 1] = arr[N - 1];
minSuffix[N - 1] = arr[N - 1];
// Constructing the maxSuffix and
// minSuffix arrays
// Traverse the array
for (int i = N - 2; i >= 0; --i) {
maxSuffix[i]
= Math.Max(maxSuffix[i + 1], arr[i]);
minSuffix[i]
= Math.Min(minSuffix[i + 1], arr[i]);
}
// Stores the maximum and minimum
// in the prefix subarray [0 .. i-1]
int maxPrefix = arr[0];
int minPrefix = arr[0];
// Store the minimum difference
int minDiff = maxSuffix[K] - minSuffix[K];
// Traverse the array
for (int i = 1; i < N; ++i) {
// If the suffix doesn't exceed
// the end of the array
if (i + K <= N) {
// Store the maximum element
// in array after removing
// subarray of size K
int maximum
= Math.Max(maxSuffix[i + K], maxPrefix);
// Stores the maximum element
// in array after removing
// subarray of size K
int minimum
= Math.Min(minSuffix[i + K], minPrefix);
// Update minimum difference
minDiff
= Math.Min(minDiff, maximum - minimum);
}
// Updating the maxPrefix and
// minPrefix with current element
maxPrefix = Math.Max(maxPrefix, arr[i]);
minPrefix = Math.Min(minPrefix, arr[i]);
}
// Print the minimum difference
Console.WriteLine(minDiff);
}
// Driver Code
public static void Main()
{
List<int> arr
= new List<int>() { 4, 5, 8, 9, 1, 2 };
int K = 2;
minimiseDifference(arr, K);
}
}
// This code is contributed by chitranayal.
Javascript
<script>
// JavaScript program for the above approach
// Function to minimize difference
// between maximum and minimum array
// elements by removing a K-length subarray
function minimiseDifference(arr, K)
{
// Size of array
var N = arr.length;
// Stores the maximum and minimum
// in the suffix subarray [i .. N-1]
var maxSuffix = new Array(N + 1);
var minSuffix = new Array(N + 1);
maxSuffix[N] = -1e9;
minSuffix[N] = 1e9;
maxSuffix[N - 1] = arr[N - 1];
minSuffix[N - 1] = arr[N - 1];
// Constructing the maxSuffix and
// minSuffix arrays
// Traverse the array
for (var i = N - 2; i >= 0; --i) {
maxSuffix[i] = Math.max(maxSuffix[i + 1], arr[i]);
minSuffix[i] = Math.min(minSuffix[i + 1], arr[i]);
}
// Stores the maximum and minimum
// in the prefix subarray [0 .. i-1]
var maxPrefix = arr[0];
var minPrefix = arr[0];
// Store the minimum difference
var minDiff = maxSuffix[K] - minSuffix[K];
// Traverse the array
for (var i = 1; i < N; ++i) {
// If the suffix doesn't exceed
// the end of the array
if (i + K <= N) {
// Store the maximum element
// in array after removing
// subarray of size K
var maximum =
Math.max(maxSuffix[i + K], maxPrefix);
// Stores the maximum element
// in array after removing
// subarray of size K
var minimum =
Math.min(minSuffix[i + K], minPrefix);
// Update minimum difference
minDiff =
Math.min(minDiff, maximum - minimum);
}
// Updating the maxPrefix and
// minPrefix with current element
maxPrefix = Math.max(maxPrefix, arr[i]);
minPrefix = Math.min(minPrefix, arr[i]);
}
// Print the minimum difference
document.write( minDiff + "<br>");
}
var arr = [ 4, 5, 8, 9, 1, 2 ];
var K = 2;
minimiseDifference(arr, K);
// This code is contributed by SoumikMondal
</script>
Producción
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA