Dada una array arr[] que consta de N enteros, la tarea es eliminar repetidamente los elementos que son más pequeños que el siguiente elemento.
Ejemplos:
Entrada: arr[] = {20, 10, 25, 30, 40}
Salida: 40
Explicación:
A continuación se muestran las operaciones que se realizan:
- Array actual: arr[] = {20, 10, 25, 30, 40}
Actualmente, arr[1](= 10) es menor que arr[2](= 25). Por lo tanto, eliminar arr[1] modifica la array a {20, 25, 30, 40}.- Actualmente arr[0](= 20) es menor que arr[1](= 25). Por lo tanto, eliminar arr[0] modifica la array a {25, 30, 40}.
- Actualmente, arr[0](= 25) es menor que arr[1](= 30). Por lo tanto, eliminar arr[0] modifica la array a {30, 40}.
- Actualmente, arr[0](= 30) es menor que arr[1](= 40). Por lo tanto, eliminar arr[0] modifica la array a {40}.
Por lo tanto, la array restante es arr[] = {40}.
Entrada: arr[] = {2, 5, 1, 0}
Salida: 5 1 0
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array y eliminar el elemento si hay elementos mayores en el rango [i + 1, N – 1] .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: iterativo: el enfoque anterior se puede optimizar recorriendo la array desde el final y realizando un seguimiento del elemento más grande encontrado y eliminando el elemento actual si es menor que el elemento más grande. Siga los pasos a continuación para resolver el problema:
- Inicialice un vector, digamos res , para almacenar la array resultante.
- Inicialice una variable, digamos maxi como INT_MIN , para almacenar el valor máximo desde el final.
- Recorra la array arr[] de manera inversa y realice los siguientes pasos:
- Si el valor de arr[i] es menor que el maxi , continúe .
- De lo contrario, inserte el elemento arr[i] en res y actualice el valor de maxi al máximo de maxi y arr[i] .
- Invierta el vector res .
- Después de completar los pasos anteriores, imprima el vector res como resultado.
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 length of an
// array by repeatedly removing elements
// that are smaller than the next element
void DeleteSmaller(int arr[], int N)
{
// Stores the maximum value in
// the range [i, N]
int maxi = INT_MIN;
// Stores the resultant array
vector<int> res;
// Iterate until i is atleast 0
for (int i = N - 1; i >= 0; i--) {
// If arr[i] is less than maxi
if (arr[i] < maxi)
continue;
// Push the arr[i] in res
res.push_back(arr[i]);
// Update the value of maxi
maxi = max(maxi, arr[i]);
}
// Reverse the vector res
reverse(res.begin(), res.end());
// Print the vector res
for (auto x : res)
cout << x << " ";
}
// Driver Code
int main()
{
int arr[] = { 2, 5, 1, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
DeleteSmaller(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to minimize length of an
// array by repeatedly removing elements
// that are smaller than the next element
static void DeleteSmaller(int arr[], int N)
{
// Stores the maximum value in
// the range [i, N]
int maxi = Integer.MIN_VALUE;
// Stores the resultant array
List<Integer> res = new ArrayList<Integer>();
// Iterate until i is atleast 0
for (int i = N - 1; i >= 0; i--) {
// If arr[i] is less than maxi
if (arr[i] < maxi)
continue;
// Push the arr[i] in res
res.add(arr[i]);
// Update the value of maxi
maxi = Math.max(maxi, arr[i]);
}
// Reverse the vector res
Collections.reverse(res);
// Print the vector res
for(int i = 0; i < res.size(); i++)
System.out.println(res.get(i) + " ");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 5, 1, 0 };
int N = arr.length;
DeleteSmaller(arr, N);
}
}
// This code is contributed by Samim Hossain Mondal
Python3
# Python3 program for the above approach # Function to minimize length of an # array by repeatedly removing elements # that are smaller than the next element def DeleteSmaller(arr, N): # Stores the maximum value in # the range [i, N] maxi =-10**9 # Stores the resultant array res = [] # Iterate until i is atleast 0 for i in range(N - 1, -1, -1): # If arr[i] is less than maxi if (arr[i] < maxi): continue # Push the arr[i] in res res.append(arr[i]) # Update the value of maxi maxi = max(maxi, arr[i]) # Reverse the vector res res = res[::-1] # Print vector res print(*res) # Driver Code if __name__ == '__main__': arr = [2, 5, 1, 0] N = len(arr) DeleteSmaller(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to minimize length of an
// array by repeatedly removing elements
// that are smaller than the next element
static void DeleteSmaller(int[] arr, int N)
{
// Stores the maximum value in
// the range [i, N]
int maxi = Int32.MinValue;
// Stores the resultant array
List<int> res = new List<int>();
// Iterate until i is atleast 0
for (int i = N - 1; i >= 0; i--) {
// If arr[i] is less than maxi
if (arr[i] < maxi)
continue;
// Push the arr[i] in res
res.Add(arr[i]);
// Update the value of maxi
maxi = Math.Max(maxi, arr[i]);
}
// Reverse the vector res
res.Reverse();
// Print the vector res
foreach(int x in res)
Console.Write(x + " ");
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 5, 1, 0 };
int N = arr.Length;
DeleteSmaller(arr, N);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program for the above approach
// Function to minimize length of an
// array by repeatedly removing elements
// that are smaller than the next element
function DeleteSmaller(arr, N)
{
// Stores the maximum value in
// the range [i, N]
let maxi = Number.MIN_SAFE_INTEGER;
// Stores the resultant array
let res = [];
// Iterate until i is atleast 0
for (let i = N - 1; i >= 0; i--) {
// If arr[i] is less than maxi
if (arr[i] < maxi)
continue;
// Push the arr[i] in res
res.push(arr[i]);
// Update the value of maxi
maxi = Math.max(maxi, arr[i]);
}
// Reverse the vector res
res.reverse();
// Print the vector res
for (let x of res)
document.write(x + " ");
}
// Driver Code
let arr = [2, 5, 1, 0];
let N = arr.length;
DeleteSmaller(arr, N);
// This code is contributed by gfgking.
</script>
Producción
5 1 0
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque eficiente: recursivo: el enfoque anterior también se puede implementar mediante la recursividad . Siga los pasos a continuación para resolver el problema:
- Inicialice un vector , diga res para almacenar la array resultante.
- Defina una función recursiva , diga RecursiveDeleteFunction(int i) para eliminar el elemento más pequeño que el siguiente elemento:
- Si el valor de i es igual a N , devuelve INT_MIN .
- Llame recursivamente a la función RecursiveDeleteFunction(i+1) y almacene el valor devuelto en una variable, digamos curr .
- Si el valor de arr[i] es al menos curr , presione arr[i] en el vector res y actualice el valor de curr como el máximo de curr y arr[i] .
- Ahora, devuelve el curr .
- Llame a la función RecursiveDeleteFunction(0) para eliminar los elementos más pequeños a los siguientes elementos y luego invierta el vector res .
- Después de completar los pasos anteriores, imprima el vector res como resultado.
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;
// Recursive function to remove
// all elements which are smaller
// than the next element
int RecursiveDeleteFunction(
int arr[], int N, int i,
vector<int>& res)
{
// If i is equal to N
if (i == N)
return INT_MIN;
// Recursive call to the next
// element
int curr = RecursiveDeleteFunction(
arr, N, i + 1, res);
// If arr[i] is greater than the
// or equal to curr
if (arr[i] >= curr) {
// Push the arr[i] in res
res.push_back(arr[i]);
// Update the value curr
curr = max(arr[i], curr);
}
// Return the value of curr
return curr;
}
// Function to minimize length of an
// array by repeatedly removing elements
// that are smaller than the next element
void DeleteSmaller(int arr[], int N)
{
// Stores maximum value in the
// the range [i, N]
int maxi = INT_MIN;
// Stores the resultant array
vector<int> res;
// Recursive call to function
// RecursiveDeleteFunction
RecursiveDeleteFunction(arr, N, 0, res);
// Reverse the vector res
reverse(res.begin(), res.end());
// Print the vector res
for (auto x : res)
cout << x << " ";
}
// Driver Code
int main()
{
int arr[] = { 2, 5, 1, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
DeleteSmaller(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Recursive function to remove
// all elements which are smaller
// than the next element
static int RecursiveDeleteFunction(
int []arr, int N, int i, ArrayList<Integer> res)
{
// If i is equal to N
if (i == N)
return Integer.MIN_VALUE;
// Recursive call to the next
// element
int curr = RecursiveDeleteFunction(
arr, N, i + 1, res);
// If arr[i] is greater than the
// or equal to curr
if (arr[i] >= curr) {
// Push the arr[i] in res
res.add(arr[i]);
// Update the value curr
curr = Math.max(arr[i], curr);
}
// Return the value of curr
return curr;
}
// Function to minimize length of an
// array by repeatedly removing elements
// that are smaller than the next element
static void DeleteSmaller(int []arr, int N)
{
// Stores maximum value in the
// the range [i, N]
int maxi = Integer.MIN_VALUE;
// Stores the resultant array
ArrayList<Integer>
res = new ArrayList<Integer>();
// Recursive call to function
// RecursiveDeleteFunction
RecursiveDeleteFunction(arr, N, 0, res);
// Reverse the vector res
Collections.reverse(res);
// Print the vector res
for (int i = 0; i < res.size(); i++)
System.out.print(res.get(i) + " ");
}
// Driver Code
public static void main(String args[])
{
int []arr = { 2, 5, 1, 0 };
int N = arr.length;
DeleteSmaller(arr, N);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python3 program for the above approach # Recursive function to remove # all elements which are smaller # than the next element def RecursiveDeleteFunction(arr, N, i, res) : # If i is equal to N if (i == N) : return -10**9 # Recursive call to the next # element curr = RecursiveDeleteFunction( arr, N, i + 1, res) # If arr[i] is greater than the # or equal to curr if (arr[i] >= curr) : # Push the arr[i] in res res.append(arr[i]) # Update the value curr curr = max(arr[i], curr) # Return the value of curr return curr # Function to minimize length of an # array by repeatedly removing elements # that are smaller than the next element def DeleteSmaller(arr, N) : # Stores maximum value in the # the range [i, N] maxi = -10**9 # Stores the resultant array res = [] # Recursive call to function # RecursiveDeleteFunction RecursiveDeleteFunction(arr, N, 0, res) # Reverse the vector res res = res[::-1] # Print the vector res for x in res : print(x, end = " ") # Driver Code if __name__ == '__main__': arr = [2, 5, 1, 0] N = len(arr) DeleteSmaller(arr, N) # This code is contributed by sanjoy_62.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Recursive function to remove
// all elements which are smaller
// than the next element
static int RecursiveDeleteFunction(
int []arr, int N, int i, List<int> res)
{
// If i is equal to N
if (i == N)
return Int32.MinValue;
// Recursive call to the next
// element
int curr = RecursiveDeleteFunction(
arr, N, i + 1, res);
// If arr[i] is greater than the
// or equal to curr
if (arr[i] >= curr) {
// Push the arr[i] in res
res.Add(arr[i]);
// Update the value curr
curr = Math.Max(arr[i], curr);
}
// Return the value of curr
return curr;
}
// Function to minimize length of an
// array by repeatedly removing elements
// that are smaller than the next element
static void DeleteSmaller(int []arr, int N)
{
// Stores maximum value in the
// the range [i, N]
int maxi = Int32.MinValue;
// Stores the resultant array
List<int> res = new List<int>();
// Recursive call to function
// RecursiveDeleteFunction
RecursiveDeleteFunction(arr, N, 0, res);
// Reverse the vector res
res.Reverse();
// Print the vector res
for (int i = 0; i < res.Count; i++)
Console.Write(res[i] + " ");
}
// Driver Code
public static void Main()
{
int []arr = { 2, 5, 1, 0 };
int N = arr.Length;
DeleteSmaller(arr, N);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Recursive function to remove
// all elements which are smaller
// than the next element
function RecursiveDeleteFunction(
arr, N, i,
res) {
// If i is equal to N
if (i == N)
return -999999999;
// Recursive call to the next
// element
let curr = RecursiveDeleteFunction(
arr, N, i + 1, res);
// If arr[i] is greater than the
// or equal to curr
if (arr[i] >= curr) {
// Push the arr[i] in res
res.push(arr[i]);
// Update the value curr
curr = Math.max(arr[i], curr);
}
// Return the value of curr
return curr;
}
// Function to minimize length of an
// array by repeatedly removing elements
// that are smaller than the next element
function DeleteSmaller(arr, N) {
// Stores maximum value in the
// the range [i, N]
let maxi = Number.MIN_VALUE;
// Stores the resultant array
let res = [];
// Recursive call to function
// RecursiveDeleteFunction
RecursiveDeleteFunction(arr, N, 0, res);
// Reverse the vector res
res.reverse();
// Print the vector res
document.write(res);
}
// Driver Code
let arr = [2, 5, 1, 0];
let N = arr.length;
DeleteSmaller(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción:
5 1 0
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por avllikhita y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA