Dada una array arr[] de enteros no negativos. Tenemos que eliminar elementos de esta array de modo que arr[i + 1] > arr[j] para cada i válido y esto se contará como un paso. Tenemos que aplicar las mismas operaciones hasta que la array se vuelva estrictamente decreciente. Ahora la tarea es contar el número de pasos necesarios para obtener la array deseada. Ejemplos:
Entrada: arr[] = {6, 5, 8, 4, 7, 10, 9} Salida: 2 Inicialmente, 8, 7 y 10 no cumplen la condición, por lo que se eliminan en el primer paso y la array se convierte en {6 , 5, 4, 9} En el siguiente paso, 9 se elimina y la array se convierte en {6, 5, 4}, que es estrictamente decreciente. Entrada: arr[] = {1, 2, 3, 4, 5} Salida: 1
Enfoque: La idea es mantener los índices de solo los elementos requeridos que se van a comparar con un elemento en particular. Por lo tanto, usamos un vector para almacenar solo los índices requeridos. Insertamos cada índice en la parte posterior y luego eliminamos los índices de la parte posterior si se cumple la siguiente condición.
arr[vect.back()] ≥ val[i]
Tomamos otra array en la que actualizamos el número de pasos que toma un elemento particular para eliminar. Si status[i] = -1 , entonces el elemento no debe eliminarse, 0 denota el primer paso y así sucesivamente…. Por eso sumaremos 1 a la respuesta. Mientras extraemos los índices, actualizamos repetidamente el estado de los elementos. Si se abren todos los índices, es decir , vect.size() = 0 , entonces este elemento no se eliminará, así que cambie su estado a -1 . A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int status[100000];
// Function to return the required
// number of steps
int countSteps(int* val, int n)
{
int sol = 0;
vector<int> vec(1, 0);
status[0] = -1;
// Compute the number of steps
for (int i = 1; i < n; ++i) {
// Current status is to
// delete in first step
status[i] = 0;
// Pop the indices while
// condition is satisfied
while (vec.size() > 0
&& val[vec.back()] >= val[i]) {
// Inserting the correct
// step no to delete
status[i] = max(status[i],
status[vec.back()] + 1);
vec.pop_back();
}
if (vec.size() == 0) {
// Status changed to not delete
status[i] = -1;
}
// Pushing a new index in the vector
vec.push_back(i);
// Build the solution from
// smaller to larger size
sol = max(sol, status[i] + 1);
}
return sol;
}
// Driver code
int main()
{
int val[] = { 6, 5, 8, 4, 7, 10, 9 };
int n = sizeof(val) / sizeof(val[0]);
cout << countSteps(val, n);
return 0;
}
Java
// A Java implementation of the approach
import java.util.*;
class GFG
{
static int []status = new int[100000];
// Function to return the required
// number of steps
static int countSteps(int[]val, int n)
{
int sol = 0;
Vector<Integer> vec = new Vector<>(1);
vec.add(0);
status[0] = -1;
// Compute the number of steps
for (int i = 1; i < n; ++i)
{
// Current status is to
// delete in first step
status[i] = 0;
// Pop the indices while
// condition is satisfied
while (vec.size() > 0
&& val[vec.lastElement()] >= val[i])
{
// Inserting the correct
// step no to delete
status[i] = Math.max(status[i],
status[vec.lastElement()] + 1);
vec.remove(vec.lastElement());
}
if (vec.isEmpty())
{
// Status changed to not delete
status[i] = -1;
}
// Pushing a new index in the vector
vec.add(i);
// Build the solution from
// smaller to larger size
sol = Math.max(sol, status[i] + 1);
}
return sol;
}
// Driver code
public static void main(String[] args)
{
int val[] = { 6, 5, 8, 4, 7, 10, 9 };
int n = val.length;
System.out.println(countSteps(val, n));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach status = [0]*100000; # Function to return the required # number of steps def countSteps(val, n) : sol = 0; vec = [1, 0]; status[0] = -1; # Compute the number of steps for i in range(n) : # Current status is to # delete in first step status[i] = 0; # Pop the indices while # condition is satisfied while (len(vec) > 0 and val[vec[len(vec)-1]] >= val[i]) : # Inserting the correct # step no to delete status[i] = max(status[i], status[len(vec)-1] + 1); vec.pop(); if (len(vec) == 0) : # Status changed to not delete status[i] = -1; # Pushing a new index in the vector vec.append(i); # Build the solution from # smaller to larger size sol = max(sol, status[i] + 1); return sol; # Driver code if __name__ == "__main__" : val = [ 6, 5, 8, 4, 7, 10, 9 ]; n = len(val); print(countSteps(val, n)); # This code is contributed by AnkitRai01
C#
// A C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static int []status = new int[100000];
// Function to return the required
// number of steps
static int countSteps(int[]val, int n)
{
int sol = 0;
List<int> vec = new List<int>(1);
vec.Add(0);
status[0] = -1;
// Compute the number of steps
for (int i = 1; i < n; ++i)
{
// Current status is to
// delete in first step
status[i] = 0;
// Pop the indices while
// condition is satisfied
while (vec.Count > 0
&& val[vec[vec.Count-1]] >= val[i])
{
// Inserting the correct
// step no to delete
status[i] = Math.Max(status[i],
status[vec[vec.Count-1]] + 1);
vec.Remove(vec[vec.Count-1]);
}
if (vec.Count == 0)
{
// Status changed to not delete
status[i] = -1;
}
// Pushing a new index in the vector
vec.Add(i);
// Build the solution from
// smaller to larger size
sol = Math.Max(sol, status[i] + 1);
}
return sol;
}
// Driver code
public static void Main(String[] args)
{
int []val = { 6, 5, 8, 4, 7, 10, 9 };
int n = val.Length;
Console.WriteLine(countSteps(val, n));
}
}
// This code contributed by Rajput-Ji
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es el número de elementos de la array.
Espacio auxiliar: O (100000), ya que estamos usando espacio adicional para el estado de la array
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA