Distancia desde el siguiente elemento mayor

Dada una array arr[] de tamaño N , la tarea es imprimir la distancia de cada elemento de la array desde su siguiente elemento mayor . Para los elementos de la array que no tienen el siguiente elemento mayor, imprima 0.

Ejemplos: 

Entrada: arr[] = {73, 74, 75, 71, 69, 72, 76, 73} 
Salida: {1, 1, 4, 2, 1, 1, 0, 0} 
Explicación: 
El siguiente elemento mayor para 73 es 74, que está en la posición 1. Distancia = 1 – 0 = 1 
El siguiente elemento mayor para 74 es 75, que está en la posición 2. Distancia = 2 – 1 = 1 
El siguiente elemento mayor para 75 es 76, que está en posición 6. Distancia = 6 – 2 = 4 
El siguiente elemento mayor para 71 es 72, que está en la posición 5. Distancia = 5 – 3 = 2 
El siguiente elemento mayor para 69 es 72, que está en la posición 5. Distancia = 5 – 4 = 1 
El siguiente elemento mayor para 72 es 76, que está en la posición 6. Distancia = 6 – 5 = 1 
No, el siguiente elemento mayor para 76. Distancia = 0 
No, el siguiente elemento mayor para 73. Distancia = 0 

Entrada: arr[] = {5, 4, 3, 2, 1} 
Salida: {0, 0, 0, 0, 0}

Enfoque ingenuo: el enfoque más simple es recorrer la array y, para cada elemento de la array, recorrer a su derecha para obtener su siguiente elemento mayor y calcular la diferencia entre los índices.

Complejidad de Tiempo: O(N 2
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar Stack para encontrar el siguiente elemento mayor. 
A continuación se muestran los pasos: 

  1. Mantenga una pila que contendrá los elementos en orden no creciente.
  2. Compruebe si el elemento actual arr[i] es mayor que el elemento en la parte superior de la pila .
  3. Siga extrayendo todos los elementos de la pila uno por uno desde la parte superior, que resulten ser más pequeños que arr[i] y calcule la distancia para cada uno de ellos como la diferencia del índice actual y el índice del elemento extraído.
  4. Empuje el elemento actual en la pila y repita los pasos anteriores.

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

C++

// C++ implementation of the
// above approach
#include<bits/stdc++.h>
using namespace std;
 
vector<int> mindistance(vector<int> arr)
{
    int N = arr.size();
     
    // Stores the required distances
    vector<int> ans(N);
    int st = 0;
     
    // Maintain a stack of elements
    // in non-increasing order
    for(int i = 0; i < N - 1; i++)
    {
        if (arr[i] < arr[i + 1])
        {
            ans[i] = 1;
        }
        else
        {
            st = i + 1;
            while (st <= N - 1)
            {
                if (arr[i] < arr[st])
                {
                    ans[i] = st - i;
                    break;
                }
                else
                {
                    st++;
                }
            }
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    vector<int> arr = { 73, 74, 75, 71,
                        69, 72, 76, 73 };
     
    vector<int> x = mindistance(arr);
     
    cout << "[";
    for(int i = 0; i < x.size(); i++)
    {
        if (i == x.size() - 1)
            cout << x[i];
        else
          cout << x[i] << ", ";
    }
    cout << "]";
}
 
// This code is contributed by SURENDRA_GANGWAR

Java

// Java implementation of the
// above approach
import java.io.*;
 
class GFG{
     
public static int[] mindistance(int[] arr)
{
    int N = arr.length;
     
    // Stores the required distances
    int[] ans = new int[N];
    int st = 0;
     
    // Maintain a stack of elements
    // in non-increasing order
    for(int i = 0; i < N - 1; i++)
    {
        if (arr[i] < arr[i + 1])
        {
            ans[i] = 1;
        }
        else
        {
            st = i + 1;
            while (st <= N - 1)
            {
                if (arr[i] < arr[st])
                {
                    ans[i] = st - i;
                    break;
                }
                else
                {
                    st++;
                }
            }
        }
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = new int[]{ 73, 74, 75, 71,
                           69, 72, 76, 73 };
     
    int x[] = mindistance(arr);
     
    System.out.print("[");
    for(int i = 0; i < x.length; i++)
        System.out.print(x[i]+", ");
         
    System.out.print("]");
}
}
 
// This code is contributed by sai-sampath mahajan
// and ramprasad kondoju

Python3

# Python3 implementation of the
# above approach
 
def mindistance(arr, N):
     
    if N <= 1:
        return [0]
       
    # Stores the required distances
    ans = [0 for i in range(N)]
    st = [0]
     
    # Maintain a stack of elements
    # in non-increasing order
    for i in range(1, N): 
         
        # If the current element exceeds
        # the element at the top of the stack
        while(st and arr[i] > arr[st[-1]]): 
            pos = st.pop()
            ans[pos] = i - pos
             
        # Push the current index to the stack
        st.append(i)
 
    return ans
 
# Given array
arr = [73, 74, 75, 71, 69, 72, 76, 73]
N = len(arr)
 
# Function call
print(mindistance(arr, N))

C#

// C# implementation of the
// above approach
using System;
 
class GFG{
     
public static int[] mindistance(int[] arr)
{
    int N = arr.Length;
     
    // Stores the required distances
    int[] ans = new int[N];
    int st = 0;
     
    // Maintain a stack of elements
    // in non-increasing order
    for(int i = 0; i < N - 1; i++)
    {
        if (arr[i] < arr[i + 1])
        {
            ans[i] = 1;
        }
        else
        {
            st = i + 1;
            while (st <= N - 1)
            {
                if (arr[i] < arr[st])
                {
                    ans[i] = st - i;
                    break;
                }
                else
                {
                    st++;
                }
            }
        }
    }
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = new int[]{ 73, 74, 75, 71,
                           69, 72, 76, 73 };
     
    int []x = mindistance(arr);
     
    Console.Write("[");
    for(int i = 0; i < x.Length; i++)
        Console.Write(x[i]+", ");
         
    Console.Write("]");
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
function mindistance(arr)
{
    let N = arr.length;
      
    // Stores the required distances
    let ans = [];
    let st = 0;
      
    // Maintain a stack of elements
    // in non-increasing order
    for(let i = 0; i < N - 1; i++)
    {
        if (arr[i] < arr[i + 1])
        {
            ans[i] = 1;
        }
        else
        {
            st = i + 1;
            while (st <= N - 1)
            {
                if (arr[i] < arr[st])
                {
                    ans[i] = st - i;
                    break;
                }
                else
                {
                    st++;
                }
            }
        }
    }
    return ans;
}
 
// Driver code
 
    let arr = [ 73, 74, 75, 71,
                           69, 72, 76, 73 ];
      
    let x = mindistance(arr);
      
    document.write("[");
    for(let i = 0; i < x.length; i++)
        document.write(x[i]+", ");
          
    document.write("]");
 
// This code is contributed by target_2.
</script>
Producción: 

[1, 1, 4, 2, 1, 1, 0, 0]

 

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por saikumarkudikala 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 *