Reduzca la array eliminando elementos que son mayores que todos los elementos a su izquierda

Dada una array arr[] de N enteros, la tarea es eliminar el elemento de la array dada si el elemento a su izquierda es más pequeño que él. Continúe eliminando los elementos de la array hasta que ningún elemento tenga un elemento izquierdo adyacente más pequeño. Imprima la array resultante después de la operación anterior.

Ejemplos: 

Entrada: arr[] = {2, 4, 1, 3, 4} 
Salida: 2 1 
Explicación: 
Dado que 4 es mayor que 2, elimine 4 y arr se convierte en {2, 1, 3, 4}. 
Ahora 3 es mayor que 1, así que quita 3 y arr se convierte en {2, 1, 4}. 
Ahora 4 es mayor que 1, así que quita 4 y arr se convierte en {2, 1}. 
Ahora ningún elemento satisface los criterios de eliminación, por lo que la array resultante es {2, 1}.

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

Enfoque: La idea es utilizar el concepto de Merge Sort .

1. Divida la array de entrada en sub-arrays hasta que el tamaño de cada sub-array sea 1.
2. Comience a fusionar el elemento.
3. Al fusionar, elimine elementos del subarreglo izquierdo hasta su elemento más a la derecha, que tengan un valor mayor que el elemento más a la izquierda del subarreglo derecho.
4. Repita los pasos anteriores en cada paso de fusión, de modo que se hayan eliminado todos los elementos con un valor más pequeño a su izquierda.
5. Finalmente imprima la array resultante.

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

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to implement merging of arr[]
vector<int> merge(vector<int> x, vector<int> y)
{
    for(auto i : y)
    {
        if (x[x.size() - 1] > i)
            x.push_back(i);
    }
    return x;
}
 
// Function to delete all elements which
// satisfy the condition A[i] > A[i-1]
vector<int> mergeDel(vector<int> l)
{
     
    // Divide array into its subarray
    if (l.size() == 1)
        return l;
 
    int m = l.size() / 2;
     
    vector<int> temp1 = {l.begin() + 0,
                         l.begin() + m};
    vector<int> temp2 = {l.begin() + m,
                         l.end()};
     
    // Getting back merged array with all 
    // its right element greater than
    // left one.
    return merge(mergeDel(temp1),
                 mergeDel(temp2));
}
 
// Driver Code
int main()
{
     
    // Given array arr[]
    vector<int> arr({ 5, 4, 3, 2, 1 });
    vector<int> ans = mergeDel(arr);
     
    cout << "[ ";
    for(auto x: ans)
        cout << x << ", ";
         
    cout << "]";
}
 
// This code is contributed by SURENDRA_GANGWAR

// Java program for the above approach
import java.util.ArrayList;
import java.util.Arrays;
 
class GFG{
     
// Function to implement merging of arr[]
static ArrayList<Integer> merge(ArrayList<Integer> x,
                                ArrayList<Integer> y)
{
    for(Integer i : y)
    {
        if (x.get(x.size() - 1) > i)
            x.add(i);
    }
    return x;
}
 
// Function to delete all elements which
// satisfy the condition A[i] > A[i-1]
static ArrayList<Integer> mergeDel(ArrayList<Integer> l)
{
     
    // Divide array into its subarray
    if (l.size() == 1)
        return l;
 
    int m = l.size() / 2;
 
    ArrayList<Integer> temp1 = new ArrayList<>(
        l.subList(0, m));
    ArrayList<Integer> temp2 = new ArrayList<>(
        l.subList(m, l.size()));
 
    // Getting back merged array with all
    // its right element greater than
    // left one.
    return merge(mergeDel(temp1), mergeDel(temp2));
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr[]
    Integer[] ar = { 5, 4, 3, 2, 1 };
     
    ArrayList<Integer> arr = new ArrayList<>(
        Arrays.asList(ar));
    ArrayList<Integer> ans = mergeDel(arr);
     
    System.out.print("[ ");
    for(Integer x : ans)
        System.out.print(x + ", ");
         
    System.out.println("]");
}
}
 
// This code is contributed by sanjeev2552

# Python3 program for the above approach
 
# Function to delete all elements which
# satisfy the condition A[i] > A[i-1]
def mergeDel(l):
 
    # Divide array into its subarray
    if len(l) == 1:
 
        return l
 
    m = int( len(l) / 2)
 
    # Getting back merged array with all
    # its right element greater than left one.
    return merge(mergeDel(l[ 0 : m ]),
                 mergeDel(l[ m : len(l)]) )
 
 
# Function to implement merging of arr[]
def merge(x, y):
 
    for i in y:
 
        if x[-1] > i :
 
            x = x + [i]
 
    return x
   
# Driver Code
 
# Function defination for main()
def main():
 
# Given array arr[]
    arr = [5, 4, 3, 2, 1]
    print(mergeDel(arr))
 
main()

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to implement merging of arr[]
static List<int> merge(List<int> x, List<int> y)
{
    foreach(int i in y)
    {
        if (x[x.Count - 1] > i)
            x.Add(i);
    }
    return x;
}
 
// Function to delete all elements which
// satisfy the condition A[i] > A[i-1]
static List<int> mergeDel(List<int> l)
{
     
    // Divide array into its subarray
    if (l.Count == 1)
        return l;
 
    int m = l.Count / 2;
 
    List<int> temp1 = l.GetRange(0, m);
    List<int> temp2 = l.GetRange(m, l.Count - m);
 
    // Getting back merged array with all
    // its right element greater than
    // left one.
    return merge(mergeDel(temp1),
                 mergeDel(temp2));
}
 
// Driver Code
public static void Main(string[] args)
{
     
    // Given array arr[]
    List<int> arr = new List<int>{ 5, 4, 3, 2, 1 };
 
    List<int> ans = mergeDel(arr);
 
    Console.Write("[ ");
    foreach(int x in ans)
        Console.Write(x + ", ");
 
    Console.Write("]");
}
}
 
// This code is contributed by chitranayal

<script>
// Javascript program for the above approach
 
// Function to implement merging of arr[]
function  merge(x,y)
{
    for(let i=0;i<y.length;i++)
    {
        if (x[x.length - 1] > y[i])
            x.push(y[i]);
    }
    return x;
}
 
// Function to delete all elements which
// satisfy the condition A[i] > A[i-1]
function mergeDel(l)
{
    // Divide array into its subarray
    if (l.length == 1)
        return l;
  
    let m = Math.floor(l.length / 2);
  
    let temp1 = l.slice(0, m);
    let temp2 = l.slice(m, l.length);
  
    // Getting back merged array with all
    // its right element greater than
    // left one.
    return merge(mergeDel(temp1), mergeDel(temp2));
}
// Driver Code
 
// Given array arr[]
let arr=[5, 4, 3, 2, 1];
let ans = mergeDel(arr);
document.write("[ ");
document.write(ans.join(", "));
document.write("]<br>");
 
 
// This code is contributed by avanitrachhadiya2155
</script>

[5, 4, 3, 2, 1]

Complejidad de tiempo: O(N*log N)  
Espacio auxiliar: O(1)