Diferencia mínima entre el elemento máximo y mínimo en todos los subarreglos de tamaño Y

Dada una array arr[] de tamaño N y entero Y , la tarea es encontrar un mínimo de todas las diferencias entre los elementos máximo y mínimo en todas las subarreglas de tamaño Y .

Ejemplos:

Entrada: arr[] = { 3, 2, 4, 5, 6, 1, 9 } Y = 3
Salida: 2
Explicación:
Todos los subarreglos de longitud = 3 son:
{3, 2, 4} donde elemento máximo = 4 y elemento mínimo = 2 diferencia = 2
{2, 4, 5} donde elemento máximo = 5 y elemento mínimo = 2 diferencia = 3
{4, 5, 6} donde elemento máximo = 6 y elemento mínimo = 4 diferencia = 2
{5, 6, 1} donde elemento máximo = 6 y elemento mínimo = 1 diferencia = 5
{6, 1, 9} donde elemento máximo = 9 y elemento mínimo = 6 diferencia = 3 
De estos, el mínimo es 2. 
 

Entrada: arr[] = { 1, 2, 3, 3, 2, 2 } Y = 4
Salida: 1
Explicación:
Todos los subarreglos de longitud = 4 son:
{1, 2, 3, 3} elemento máximo = 3 y mínimo elemento = 1 diferencia = 2
{2, 3, 3, 2} elemento máximo = 3 y elemento mínimo = 2 diferencia = 1
{3, 3, 2, 2} elemento máximo = 3 y elemento mínimo = 2 diferencia = 1 
Fuera de estos, el mínimo es 1.                          

 

Enfoque ingenuo: la idea ingenua es atravesar para cada índice i en el rango [0, N – Y] usar otro ciclo para atravesar desde el i -ésimo índice hasta (i + Y – 1) el ésimo índice y luego calcular los elementos mínimo y máximo en un subarreglo de tamaño Y y, por lo tanto, calcule la diferencia del elemento máximo y mínimo para esa i -ésima iteración. Finalmente, controlando las diferencias, evalúe la diferencia mínima.

Complejidad temporal: O(N*Y)
Espacio auxiliar: O(1)

Enfoque Eficiente: La idea es utilizar el concepto del enfoque discutido en el artículo El Siguiente Elemento Mayor . A continuación se muestran los pasos:

  1. Cree dos arrays maxarr[] y minarr[] , donde maxarr[] almacenará el índice del elemento que es el siguiente mayor al elemento en el i -ésimo índice y minarr[] almacenará el índice del siguiente elemento que es menor que el elemento en el i -ésimo índice .
  2. Inicialice una pila con 0 para almacenar los índices en los dos casos anteriores.
  3. Para cada índice, i en el rango [0, N – Y] , utilizando un bucle anidado y un enfoque de ventana deslizante, forman dos arrays submax y submin. Estos arreglos almacenarán elementos máximos y mínimos en el subarreglo en la i -ésima iteración.
  4. Finalmente, calcule la diferencia mínima.

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 get the maximum of all 
// the subarrays of size Y 
vector<int> get_submaxarr(int* arr, 
                        int n, int y) 
{ 
    int j = 0; 
    stack<int> stk; 
  
    // ith index of maxarr array 
    // will be the index upto which 
    // Arr[i] is maximum 
    vector<int> maxarr(n); 
    stk.push(0); 
  
    for (int i = 1; i < n; i++) { 
  
        // Stack is used to find the 
        // next larger element and 
        // keeps track of index of 
        // current iteration 
        while (stk.empty() == false
            and arr[i] > arr[stk.top()]) { 
  
            maxarr[stk.top()] = i - 1; 
            stk.pop(); 
        } 
        stk.push(i); 
    } 
  
    // Loop for remaining indexes 
    while (!stk.empty()) { 
  
        maxarr[stk.top()] = n - 1; 
        stk.pop(); 
    } 
    vector<int> submax; 
  
    for (int i = 0; i <= n - y; i++) { 
  
        // j < i used to keep track 
        // whether jth element is 
        // inside or outside the window 
        while (maxarr[j] < i + y - 1 
            or j < i) { 
            j++; 
        } 
  
        submax.push_back(arr[j]); 
    } 
  
    // Return submax 
    return submax; 
} 
  
// Function to get the minimum for 
// all subarrays of size Y 
vector<int> get_subminarr(int* arr, 
                        int n, int y) 
{ 
    int j = 0; 
  
    stack<int> stk; 
  
    // ith index of minarr array 
    // will be the index upto which 
    // Arr[i] is minimum 
    vector<int> minarr(n); 
    stk.push(0); 
  
    for (int i = 1; i < n; i++) { 
  
        // Stack is used to find the 
        // next smaller element and 
        // keeping track of index of 
        // current iteration 
        while (stk.empty() == false
            and arr[i] < arr[stk.top()]) { 
  
            minarr[stk.top()] = i; 
            stk.pop(); 
        } 
        stk.push(i); 
    } 
  
    // Loop for remaining indexes 
    while (!stk.empty()) { 
  
        minarr[stk.top()] = n; 
        stk.pop(); 
    } 
  
    vector<int> submin; 
  
    for (int i = 0; i <= n - y; i++) { 
  
        // j < i used to keep track 
        // whether jth element is inside 
        // or outside the window 
  
        while (minarr[j] <= i + y - 1 
            or j < i) { 
            j++; 
        } 
  
        submin.push_back(arr[j]); 
    } 
  
    // Return submin 
    return submin; 
} 
  
// Function to get minimum difference 
void getMinDifference(int Arr[], int N, 
                    int Y) 
{ 
    // Create submin and submax arrays 
    vector<int> submin 
        = get_subminarr(Arr, N, Y); 
  
    vector<int> submax 
        = get_submaxarr(Arr, N, Y); 
  
    // Store initial difference 
    int minn = submax[0] - submin[0]; 
    int b = submax.size(); 
  
    for (int i = 1; i < b; i++) { 
  
        // Calculate temporary difference 
        int dif = submax[i] - submin[i]; 
        minn = min(minn, dif); 
    } 
  
    // Final minimum difference 
    cout << minn << "\n"; 
} 
  
// Driver Code 
int main() 
{ 
    // Given array arr[] 
    int arr[] = { 1, 2, 3, 3, 2, 2 }; 
    int N = sizeof arr / sizeof arr[0]; 
  
    // Given subarray size 
    int Y = 4; 
  
    // Function Call 
    getMinDifference(arr, N, Y); 
    return 0; 
}

Java

// Java program for the above approach
import java.util.*;
  
class GFG{
  
// Function to get the maximum of all
// the subarrays of size Y
static Vector<Integer> get_submaxarr(int[] arr, int n, 
                                     int y)
{
    int j = 0;
    Stack<Integer> stk = new Stack<Integer>();
    
    // ith index of maxarr array
    // will be the index upto which
    // Arr[i] is maximum
    int[] maxarr = new int[n];
    Arrays.fill(maxarr,0);
    stk.push(0);
    
    for(int i = 1; i < n; i++) 
    {
          
        // Stack is used to find the
        // next larger element and
        // keeps track of index of
        // current iteration
        while (stk.size() != 0 && 
               arr[i] > arr[stk.peek()]) 
        {
            maxarr[stk.peek()] = i - 1;
            stk.pop();
        }
        stk.push(i);
    }
    
    // Loop for remaining indexes
    while (stk.size() != 0)
    {
        maxarr[stk.size()] = n - 1;
        stk.pop();
    }
    Vector<Integer> submax = new Vector<Integer>();
    
    for(int i = 0; i <= n - y; i++)
    {
          
        // j < i used to keep track
        // whether jth element is
        // inside or outside the window
        while (maxarr[j] < i + y - 1 || j < i) 
        {
            j++;
        }
        submax.add(arr[j]);
    }
    
    // Return submax
    return submax;
}
    
// Function to get the minimum for
// all subarrays of size Y
static Vector<Integer> get_subminarr(int[] arr, int n,
                                     int y)
{
    int j = 0;
    
    Stack<Integer> stk = new Stack<Integer>();
    
    // ith index of minarr array
    // will be the index upto which
    // Arr[i] is minimum
    int[] minarr = new int[n];
    Arrays.fill(minarr,0);
    stk.push(0);
    
    for(int i = 1; i < n; i++) 
    {
          
        // Stack is used to find the
        // next smaller element and
        // keeping track of index of
        // current iteration
        while (stk.size() != 0 && 
               arr[i] < arr[stk.peek()])
        {
            minarr[stk.peek()] = i;
            stk.pop();
        }
        stk.push(i);
    }
    
    // Loop for remaining indexes
    while (stk.size() != 0)
    {
        minarr[stk.peek()] = n;
        stk.pop();
    }
    
    Vector<Integer> submin = new Vector<Integer>();
    
    for(int i = 0; i <= n - y; i++)
    {
          
        // j < i used to keep track
        // whether jth element is inside
        // or outside the window
    
        while (minarr[j] <= i + y - 1 || j < i) 
        {
            j++;
        }
        submin.add(arr[j]);
    }
    
    // Return submin
    return submin;
}
    
// Function to get minimum difference
static void getMinDifference(int[] Arr, int N, int Y)
{
      
    // Create submin and submax arrays
    Vector<Integer> submin = get_subminarr(Arr, N, Y);
    
    Vector<Integer> submax = get_submaxarr(Arr, N, Y);
    
    // Store initial difference
    int minn = submax.get(0) - submin.get(0);
    int b = submax.size();
    
    for(int i = 1; i < b; i++) 
    {
          
        // Calculate temporary difference
        int dif = submax.get(i) - submin.get(i) + 1;
        minn = Math.min(minn, dif);
    }
    
    // Final minimum difference
    System.out.print(minn);
}
  
// Driver code
public static void main(String[] args)
{
      
    // Given array arr[]
    int[] arr = { 1, 2, 3, 3, 2, 2 };
    int N = arr.length;
    
    // Given subarray size
    int Y = 4;
    
    // Function Call
    getMinDifference(arr, N, Y);
}
}
  
// This code is contributed by decode2207

Python3

# Python3 program for the above approach 
  
# Function to get the maximum of all 
# the subarrays of size Y 
def get_submaxarr(arr, n, y): 
      
    j = 0
    stk = []
      
    # ith index of maxarr array 
    # will be the index upto which 
    # Arr[i] is maximum 
    maxarr = [0] * n 
    stk.append(0) 
  
    for i in range(1, n):
  
        # Stack is used to find the 
        # next larger element and 
        # keeps track of index of 
        # current iteration 
        while (len(stk) > 0 and 
                 arr[i] > arr[stk[-1]]):
            maxarr[stk[-1]] = i - 1
            stk.pop() 
              
        stk.append(i)
  
    # Loop for remaining indexes 
    while (stk):
        maxarr[stk[-1]] = n - 1
        stk.pop()
          
    submax = [] 
      
    for i in range(n - y + 1):
  
        # j < i used to keep track 
        # whether jth element is 
        # inside or outside the window 
        while (maxarr[j] < i + y - 1 or
                       j < i):
            j += 1
              
        submax.append(arr[j])
  
    # Return submax 
    return submax
  
# Function to get the minimum for 
# all subarrays of size Y 
def get_subminarr(arr, n, y):
      
    j = 0
    stk = [] 
      
    # ith index of minarr array 
    # will be the index upto which 
    # Arr[i] is minimum 
    minarr = [0] * n
    stk.append(0)
      
    for i in range(1 , n):
          
        # Stack is used to find the 
        # next smaller element and 
        # keeping track of index of 
        # current iteration 
        while (stk and arr[i] < arr[stk[-1]]):
            minarr[stk[-1]] = i
            stk.pop() 
              
        stk.append(i) 
          
    # Loop for remaining indexes 
    while (stk):
        minarr[stk[-1]] = n
        stk.pop()
          
    submin = []
      
    for i in range(n - y + 1):
          
        # j < i used to keep track 
        # whether jth element is inside 
        # or outside the window 
        while (minarr[j] <= i + y - 1 or
                      j < i):
            j += 1
              
        submin.append(arr[j])
          
    # Return submin 
    return submin 
  
# Function to get minimum difference 
def getMinDifference(Arr, N, Y):
      
    # Create submin and submax arrays
    submin = get_subminarr(Arr, N, Y)
    submax = get_submaxarr(Arr, N, Y)
      
    # Store initial difference 
    minn = submax[0] - submin[0]
    b = len(submax)
      
    for i in range(1, b):
          
        # Calculate temporary difference 
        diff = submax[i] - submin[i]
        minn = min(minn, diff)
      
    # Final minimum difference 
    print(minn)
      
# Driver code
  
# Given array arr[]
arr = [ 1, 2, 3, 3, 2, 2 ]
N = len(arr)
  
# Given subarray size
Y = 4
  
# Function call
getMinDifference(arr, N, Y)
      
# This code is contributed by Stuti Pathak

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
      
    // Function to get the maximum of all
    // the subarrays of size Y
    static List<int> get_submaxarr(int[] arr, int n, int y)
    {
        int j = 0;
        Stack<int> stk = new Stack<int>();
       
        // ith index of maxarr array
        // will be the index upto which
        // Arr[i] is maximum
        int[] maxarr = new int[n];
        Array.Fill(maxarr,0);
        stk.Push(0);
       
        for (int i = 1; i < n; i++) {
       
            // Stack is used to find the
            // next larger element and
            // keeps track of index of
            // current iteration
            while (stk.Count!=0 && arr[i] > arr[stk.Peek()]) {
       
                maxarr[stk.Peek()] = i - 1;
                stk.Pop();
            }
            stk.Push(i);
        }
       
        // Loop for remaining indexes
        while (stk.Count!=0) {
       
            maxarr[stk.Count] = n - 1;
            stk.Pop();
        }
        List<int> submax = new List<int>();
       
        for (int i = 0; i <= n - y; i++) {
       
            // j < i used to keep track
            // whether jth element is
            // inside or outside the window
            while (maxarr[j] < i + y - 1
                || j < i) {
                j++;
            }
       
            submax.Add(arr[j]);
        }
       
        // Return submax
        return submax;
    }
       
    // Function to get the minimum for
    // all subarrays of size Y
    static List<int> get_subminarr(int[] arr, int n, int y)
    {
        int j = 0;
       
        Stack<int> stk = new Stack<int>();
       
        // ith index of minarr array
        // will be the index upto which
        // Arr[i] is minimum
        int[] minarr = new int[n];
        Array.Fill(minarr,0);
        stk.Push(0);
       
        for (int i = 1; i < n; i++) {
       
            // Stack is used to find the
            // next smaller element and
            // keeping track of index of
            // current iteration
            while (stk.Count!=0
                && arr[i] < arr[stk.Peek()]) {
       
                minarr[stk.Peek()] = i;
                stk.Pop();
            }
            stk.Push(i);
        }
       
        // Loop for remaining indexes
        while (stk.Count!=0) {
       
            minarr[stk.Peek()] = n;
            stk.Pop();
        }
       
        List<int> submin = new List<int>();
       
        for (int i = 0; i <= n - y; i++) {
       
            // j < i used to keep track
            // whether jth element is inside
            // or outside the window
       
            while (minarr[j] <= i + y - 1
                || j < i) {
                j++;
            }
       
            submin.Add(arr[j]);
        }
       
        // Return submin
        return submin;
    }
       
    // Function to get minimum difference
    static void getMinDifference(int[] Arr, int N, int Y)
    {
        // Create submin and submax arrays
        List<int> submin
            = get_subminarr(Arr, N, Y);
       
        List<int> submax
            = get_submaxarr(Arr, N, Y);
       
        // Store initial difference
        int minn = submax[0] - submin[0];
        int b = submax.Count;
       
        for (int i = 1; i < b; i++) {
       
            // Calculate temporary difference
            int dif = submax[i] - submin[i] + 1;
            minn = Math.Min(minn, dif);
        }
       
        // Final minimum difference
        Console.WriteLine(minn);
    }
  
  static void Main() {
    // Given array arr[]
    int[] arr = { 1, 2, 3, 3, 2, 2 };
    int N = arr.Length;
   
    // Given subarray size
    int Y = 4;
   
    // Function Call
    getMinDifference(arr, N, Y);
  }
}
  
// This code is contributed by rameshtravel07.

Javascript

<script>
  
// Javascript program for the above approach 
  
// Function to get the maximum of all 
// the subarrays of size Y 
function get_submaxarr(arr, n, y) 
{ 
    var j = 0; 
    var stk = []; 
  
    // ith index of maxarr array 
    // will be the index upto which 
    // Arr[i] is maximum 
    var maxarr = Array(n); 
    stk.push(0); 
  
    for (var i = 1; i < n; i++) { 
  
        // Stack is used to find the 
        // next larger element and 
        // keeps track of index of 
        // current iteration 
        while (stk.length!=0
            && arr[i] > arr[stk[stk.length-1]]) { 
  
            maxarr[stk[stk.length-1]] = i - 1; 
            stk.pop(); 
        } 
        stk.push(i); 
    } 
  
    // Loop for remaining indexes 
    while (stk.length!=0) { 
  
        maxarr[stk[stk.length-1]] = n - 1; 
        stk.pop(); 
    } 
    var submax = []; 
  
    for (var i = 0; i <= n - y; i++) { 
  
        // j < i used to keep track 
        // whether jth element is 
        // inside or outside the window 
        while (maxarr[j] < i + y - 1 
            || j < i) { 
            j++; 
        } 
  
        submax.push(arr[j]); 
    } 
  
    // Return submax 
    return submax; 
} 
  
// Function to get the minimum for 
// all subarrays of size Y 
function get_subminarr(arr, n, y) 
{ 
    var j = 0; 
  
    var stk = []; 
  
    // ith index of minarr array 
    // will be the index upto which 
    // Arr[i] is minimum 
    var minarr = Array(n); 
    stk.push(0); 
  
    for (var i = 1; i < n; i++) { 
  
        // Stack is used to find the 
        // next smaller element and 
        // keeping track of index of 
        // current iteration 
        while (stk.length!=0
            && arr[i] < arr[stk[stk.length-1]]) { 
  
            minarr[stk[stk.length-1]] = i; 
            stk.pop(); 
        } 
        stk.push(i); 
    } 
  
    // Loop for remaining indexes 
    while (stk.length!=0) { 
  
        minarr[stk[stk.length-1]] = n; 
        stk.pop(); 
    } 
  
    var submin = []; 
  
    for (var i = 0; i <= n - y; i++) { 
  
        // j < i used to keep track 
        // whether jth element is inside 
        // or outside the window 
  
        while (minarr[j] <= i + y - 1 
            || j < i) { 
            j++; 
        } 
  
        submin.push(arr[j]); 
    } 
  
    // Return submin 
    return submin; 
} 
  
// Function to get minimum difference 
function getMinDifference(Arr, N, Y) 
{ 
    // Create submin and submax arrays 
    var submin 
        = get_subminarr(Arr, N, Y); 
  
    var submax 
        = get_submaxarr(Arr, N, Y); 
  
    // Store initial difference 
    var minn = submax[0] - submin[0]; 
    var b = submax.length; 
  
    for (var i = 1; i < b; i++) { 
  
        // Calculate temporary difference 
        var dif = submax[i] - submin[i]; 
        minn = Math.min(minn, dif); 
    } 
  
    // Final minimum difference 
    document.write( minn + "<br>"); 
} 
  
// Driver Code 
// Given array arr[] 
var arr = [1, 2, 3, 3, 2, 2]; 
var N = arr.length 
// Given subarray size 
var Y = 4; 
// Function Call 
getMinDifference(arr, N, Y); 
  
  
</script>
Producción: 

1

 

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 abhijeet010304 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *