Pasos mínimos necesarios para hacer una array decreciente

Dada una array arr[] , la tarea es encontrar los pasos mínimos necesarios para hacer que una array disminuya, donde en cada paso se eliminan todos los elementos que son mayores que los elementos de su elemento izquierdo.
Ejemplos: 
 

Entrada: arr[] = {3, 2, 1, 7, 5} 
Salida: 2 
Explicación: 
En la array anterior se requieren dos pasos para hacer que la array disminuya – 
Paso 1: En el paso 1 hay un elemento que es mayor que su izquierda, es decir, 7 > 1. 
Paso 2: En el paso 2 hay un elemento que es mayor que su izquierda, es decir, 5 > 1.
Entrada: arr[] = {6, 5, 8, 4, 7, 10 , 9} 
Salida: 2 
En la array anterior se requieren dos pasos para que la array disminuya – 
Paso 1: En el paso 1 hay tres elementos que son mayores que su izquierda, que es 8 > 5, 7 > 4 y 10 > 7 Paso 2 : 
En el paso 2 hay tres, es solo un elemento que es mayor que su izquierda, que es 9> 4. 
 

Enfoque ingenuo: itere sobre la array y cuente los elementos que son mayores que su izquierda, si el elemento no es mayor que su izquierda, empuje el elemento a otra array (por ejemplo, arr1 ) y después de la iteración completa de la array, copie todos los elementos de arr1 a la array inicial y repita el mismo procedimiento hasta que el recuento de elementos eliminados en un paso sea 0. Este enfoque toma tiempo O(N ² ) en el peor de los casos y espacio O(N).
Enfoque eficiente: la idea es usar una pila y empujar el elemento dentro de la pila solo si el elemento es mayor que su elemento anterior, de lo contrario, cuente la cantidad de escaneos y salte. 
Solo nos importan los elementos que son más pequeños.
 

//C++ implementation to make an
// array decreasing
 
#include<bits/stdc++.h>
using namespace std;
 
// Structure to store elements
struct Node
{
    int elementID;
    int stepsToeliminate;
};
 
// Function to find the
// minimum steps required
void minSteps(int arr[], int N)
{
    stack<Node> s;
     
    s.push({ 0, -1 });
     
    // Minimum steps
    int maxStepsToeliminate = -1;
     
    // Loop to iterate
    // over the array
    for (int i = 1; i < N; i++)
    {
        int stepsToeliminate = 1;
         
        // Traversing the stack until
        // it is not empty
        while (!s.empty())
        {
            // Condition if the top of the
            // stack is greater than the
            // current element
            if (arr[s.top().elementID] >=
                                   arr[i])
            {
                stepsToeliminate = max(stepsToeliminate,
                           s.top().stepsToeliminate + 1);
                s.pop();
            }
            else
            {
                break;
            }
        }
         
        // Condition if no previous
        // elements value less than
        // this element then steps is -1
        if (s.empty())
        {
            stepsToeliminate = -1;
        }
     
        maxStepsToeliminate = max(
            maxStepsToeliminate, stepsToeliminate
            );
        s.push({ i, stepsToeliminate });
    }
     
    cout << (maxStepsToeliminate < 0 ? 0 :
              maxStepsToeliminate) << endl;
}
 
// Driver Code
int main()
{
    int arr[] = {3, 2, 1, 7, 5};
     
    int size = sizeof(arr)/sizeof(arr[0]);
     
    minSteps(arr, size);
     
    return 0;
}

// Java implementation to make an
// array decreasing
import java.util.*;
 
class GFG{
  
// Structure to store elements
static class Node
{
    int elementID;
    int stepsToeliminate;
    public Node(int elementID, int stepsToeliminate) {
        super();
        this.elementID = elementID;
        this.stepsToeliminate = stepsToeliminate;
    }
     
};
  
// Function to find the
// minimum steps required
static void minSteps(int arr[], int N)
{
    Stack<Node> s = new Stack<Node>();
      
    s.add(new Node( 0, -1 ));
      
    // Minimum steps
    int maxStepsToeliminate = -1;
      
    // Loop to iterate
    // over the array
    for (int i = 1; i < N; i++)
    {
        int stepsToeliminate = 1;
          
        // Traversing the stack until
        // it is not empty
        while (!s.isEmpty())
        {
            // Condition if the top of the
            // stack is greater than the
            // current element
            if (arr[s.peek().elementID] >=
                                   arr[i])
            {
                stepsToeliminate = Math.max(stepsToeliminate,
                           s.peek().stepsToeliminate + 1);
                s.pop();
            }
            else
            {
                break;
            }
        }
          
        // Condition if no previous
        // elements value less than
        // this element then steps is -1
        if (s.isEmpty())
        {
            stepsToeliminate = -1;
        }
      
        maxStepsToeliminate = Math.max(
            maxStepsToeliminate, stepsToeliminate
            );
        s.add(new Node(i, stepsToeliminate ));
    }
      
    System.out.print((maxStepsToeliminate < 0 ? 0 :
              maxStepsToeliminate) +"\n");
}
  
// Driver Code
public static void main(String[] args)
{
    int arr[] = {3, 2, 1, 7, 5};
      
    int size = arr.length;
      
    minSteps(arr, size);    
}
}
 
// This code is contributed by sapnasingh4991

# Python3 implementation to make an
# array decreasing
 
# Function to find the
# minimum steps required
def minSteps(arr,  N) :
 
    s = [];
     
    s.append(( 0, -1 ));
     
    # Minimum steps
    maxStepsToeliminate = -1;
     
    # Loop to iterate
    # over the array
    for i in range(1, N) :
     
        stepsToeliminate = 1;
         
        # Traversing the stack until
        # it is not empty
        while (len(s) != 0) :
 
            # Condition if the top of the
            # stack is greater than the
            # current element
            if (arr[s[-1][0]] >= arr[i]) :
                stepsToeliminate = max(stepsToeliminate, s[-1][1] + 1);
                s.pop();
         
            else :
             
                break;
     
        # Condition if no previous
        # elements value less than
        # this element then steps is -1
        if (len(s) == 0) :
         
            stepsToeliminate = -1;
     
     
        maxStepsToeliminate = max( maxStepsToeliminate, stepsToeliminate );
         
        s.append(( i, stepsToeliminate ));
     
    print(  0 if (maxStepsToeliminate < 0 ) else  maxStepsToeliminate );
 
 
# Driver Code
if __name__ == "__main__" :
 
    arr = [3, 2, 1, 7, 5];
     
    size = len(arr);
     
    minSteps(arr, size);
     
# This code is contributed by AnkitRai01

// C# implementation to make an
// array decreasing
using System;
using System.Collections.Generic;
 
class GFG{
   
// Structure to store elements
class Node
{
    public int elementID;
    public int stepsToeliminate;
    public Node(int elementID, int stepsToeliminate) {
        this.elementID = elementID;
        this.stepsToeliminate = stepsToeliminate;
    }
      
};
   
// Function to find the
// minimum steps required
static void minSteps(int []arr, int N)
{
    Stack<Node> s = new Stack<Node>();
       
    s.Push(new Node( 0, -1 ));
       
    // Minimum steps
    int maxStepsToeliminate = -1;
       
    // Loop to iterate
    // over the array
    for (int i = 1; i < N; i++)
    {
        int stepsToeliminate = 1;
           
        // Traversing the stack until
        // it is not empty
        while (s.Count!=0)
        {
            // Condition if the top of the
            // stack is greater than the
            // current element
            if (arr[s.Peek().elementID] >=
                                   arr[i])
            {
                stepsToeliminate = Math.Max(stepsToeliminate,
                           s.Peek().stepsToeliminate + 1);
                s.Pop();
            }
            else
            {
                break;
            }
        }
           
        // Condition if no previous
        // elements value less than
        // this element then steps is -1
        if (s.Count!=0)
        {
            stepsToeliminate = -1;
        }
       
        maxStepsToeliminate = Math.Max(
            maxStepsToeliminate, stepsToeliminate
            );
        s.Push(new Node(i, stepsToeliminate ));
    }
       
    Console.Write((maxStepsToeliminate < 0 ? 0 :
              maxStepsToeliminate) +"\n");
}
   
// Driver Code
public static void Main(String[] args)
{
    int []arr = {3, 2, 1, 7, 5};
       
    int size = arr.Length;
       
    minSteps(arr, size);    
}
}
  
// This code is contributed by PrinciRaj1992

<script>
    // Javascript implementation to make an array decreasing
     
    // Structure to store elements
    class Node
    {
        constructor(elementID, stepsToeliminate) {
           this.elementID = elementID;
           this.stepsToeliminate = stepsToeliminate;
        }
    }
     
    // Function to find the
    // minimum steps required
    function minSteps(arr, N)
    {
        let s = [];
 
        s.push(new Node( 0, -1 ));
 
        // Minimum steps
        let maxStepsToeliminate = -1;
 
        // Loop to iterate
        // over the array
        for (let i = 1; i < N; i++)
        {
            let stepsToeliminate = 1;
 
            // Traversing the stack until
            // it is not empty
            while (s.length!=0)
            {
                // Condition if the top of the
                // stack is greater than the
                // current element
                if (arr[s[s.length - 1].elementID] >= arr[i])
                {
                    stepsToeliminate = Math.max(stepsToeliminate,
                               s[s.length - 1].stepsToeliminate + 1);
                    s.pop();
                }
                else
                {
                    break;
                }
            }
 
            // Condition if no previous
            // elements value less than
            // this element then steps is -1
            if (s.length!=0)
            {
                stepsToeliminate = -1;
            }
 
            maxStepsToeliminate = Math.max(maxStepsToeliminate, stepsToeliminate);
            s.push(new Node(i, stepsToeliminate ));
        }
 
        document.write((maxStepsToeliminate < 0 ? 0 :
                  maxStepsToeliminate) +"</br>");
    }
     
    let arr = [3, 2, 1, 7, 5];
         
    let size = arr.length;
         
    minSteps(arr, size);
     
    // This code is contributed by rameshtravel07.
</script>

2

Análisis de rendimiento: 
 

• Complejidad de tiempo: como en el enfoque anterior, hay un ciclo que toma tiempo O (N), por lo tanto, la complejidad de tiempo será O (N) .
• Complejidad del espacio: como en el enfoque anterior, se usa una pila para almacenar los elementos anteriores, por lo que la complejidad del espacio será O(N) .