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 = 0Entrada: 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:
- Mantenga una pila que contendrá los elementos en orden no creciente.
- Compruebe si el elemento actual arr[i] es mayor que el elemento en la parte superior de la pila .
- 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.
- 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>
[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