Dada una array arr[] que representa una secuencia de montones de cajas donde todas y cada una de las cajas tienen la misma altura de 1 unidad. Dado que está en la parte superior de la primera pila y necesita llegar al suelo moviéndose de cada pila comenzando de izquierda a derecha.
Restricciones :
- Uno puede pasar de la pila actual de cajas a la siguiente cuando la altura de la siguiente pila es igual o menor que la altura de la pila en la que se encuentra.
- También se pueden encontrar algunas pilas cuya altura es mayor que la pila sobre la que están parados. Por lo tanto, deberán eliminar algunas cajas de esa pila para avanzar. Entonces, la tarea es decir la cantidad total de cajas que se deben quitar de cada pila (si es necesario) durante el viaje al suelo.
Se da la altura de todas las pilas. Suponga que está parado en la primera pila. Imprime el número total de cajas a retirar.
Ejemplos :
Entrada : arr[] = {3, 3, 2, 4, 1}
Salida : 2
Explicación : después de quitar las cajas, las alturas de las pilas serán {3, 3, 2, 2, 1}
Actualmente estamos parados en el 1er. montón de altura 3.
Paso 1 : Podemos pasar al segundo montón, ya que su altura es igual a la altura del montón actual.
Paso 2 : Podemos pasar a la 3.ª pila de altura 2, ya que es menor que 3.
Paso 3 : No podemos pasar de la 3.ª pila a la 4.ª pila (de altura 4), por lo que tenemos que sacar 2 cajas de la 4.ª pila para haga que su altura sea igual a 2.
Paso 4 : podemos movernos fácilmente a la última pila ya que su altura es 1, que es menor que la altura de la cuarta pila de altura 2 (eliminando 2 cajas en el paso anterior).
Entrada : arr[] = {5, 6, 7, 1}
Salida : 3
Explicación : después de quitar las cajas, las alturas de las pilas serán {5, 5, 5, 1}
Actualmente estamos parados en la primera pila de altura 5
Paso 1 : No podemos pasar a la 2ª pila ya que su altura es mayor. Entonces, quitamos 1 caja y hacemos que su altura sea igual a 5 y luego avanzamos.
Paso 2 : No podemos pasar a la 3ª pila de altura 7, por lo que le quitamos 2 cajas.
Paso 3 : podemos movernos fácilmente a la última pila ya que su altura es 1, que es menor que la altura de la tercera pila de altura 5.
La idea es atravesar la array comenzando desde la izquierda y cada vez antes de avanzar, compare la altura de la pila actual con la pila anterior. Si la altura de la pila actual es mayor que la pila anterior, incremente el conteo por la diferencia de las dos alturas; de lo contrario, avance en la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number of
// boxes to be removed
#include <bits/stdc++.h>
using namespace std;
// Function to find the number of
// boxes to be removed
int totalBoxesRemoved(int arr[], int n)
{
int count = 0;
// Store height of previous pile
int prev = arr[0];
// Start traversing the array
for (int i = 1; i < n; i++) {
// if height of current pile is greater
// than previous pile
if (arr[i] > prev) {
// Increment count by difference
// of two heights
count += (arr[i] - prev);
// Update current height
arr[i] = prev;
// Update prev for next iteration
prev = arr[i];
}
else {
// Update prev for next iteration
prev = arr[i];
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 5, 4, 7, 3, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << totalBoxesRemoved(arr, n);
return 0;
}
Java
// Java program to find the number of
// boxes to be removed
import java.io.*;
class GFG {
// Function to find the number of
// boxes to be removed
static int totalBoxesRemoved(int arr[], int n)
{
int count = 0;
// Store height of previous pile
int prev = arr[0];
// Start traversing the array
for (int i = 1; i < n; i++) {
// if height of current pile is greater
// than previous pile
if (arr[i] > prev) {
// Increment count by difference
// of two heights
count += (arr[i] - prev);
// Update current height
arr[i] = prev;
// Update prev for next iteration
prev = arr[i];
}
else {
// Update prev for next iteration
prev = arr[i];
}
}
return count;
}
// Driver code
public static void main (String[] args) {
int arr[] = { 5, 4, 7, 3, 2, 1 };
int n = arr.length;
System.out.println(totalBoxesRemoved(arr, n));
}
}
// This code is contributed
// by inder_verma..
Python3
# Python3 program to find the # number of boxes to be removed # Function to find the number # of boxes to be removed def totalBoxesRemoved(arr, n): count = 0 # Store height of previous pile prev = arr[0] # Start traversing the array for i in range(1, n): # if height of current pile # is greater than previous pile if (arr[i] > prev) : # Increment count by # difference of two heights count += (arr[i] - prev) # Update current height arr[i] = prev # Update prev for next # iteration prev = arr[i] else : # Update prev for next # iteration prev = arr[i] return count # Driver code arr = [ 5, 4, 7, 3, 2, 1 ] n = len(arr) print(totalBoxesRemoved(arr, n)) # This code is contributed # by Yatin Gupta
C#
// C# program to find the number of
// boxes to be removed
using System;
class GFG {
// Function to find the number of
// boxes to be removed
static int totalBoxesRemoved(int []arr, int n)
{
int count = 0;
// Store height of previous pile
int prev = arr[0];
// Start traversing the array
for (int i = 1; i < n; i++) {
// if height of current pile is greater
// than previous pile
if (arr[i] > prev) {
// Increment count by difference
// of two heights
count += (arr[i] - prev);
// Update current height
arr[i] = prev;
// Update prev for next iteration
prev = arr[i];
}
else {
// Update prev for next iteration
prev = arr[i];
}
}
return count;
}
// Driver code
public static void Main () {
int []arr = { 5, 4, 7, 3, 2, 1 };
int n = arr.Length;
Console.WriteLine(totalBoxesRemoved(arr, n));
}
}
// This code is contributed
// by shs
PHP
<?php
// PHP program to find the number
// of boxes to be removed
// Function to find the number
// of boxes to be removed
function totalBoxesRemoved($arr, $n)
{
$count = 0;
// Store height of previous pile
$prev = $arr[0];
// Start traversing the array
for ($i = 1; $i <$n; $i++)
{
// if height of current pile is
// greater than previous pile
if ($arr[$i] > $prev)
{
// Increment count by difference
// of two heights
$count += ($arr[$i] - $prev);
// Update current height
$arr[$i] = $prev;
// Update prev for next iteration
$prev = $arr[$i];
}
else
{
// Update prev for next iteration
$prev = $arr[$i];
}
}
return $count;
}
// Driver code
$arr = array( 5, 4, 7, 3, 2, 1 );
$n = count($arr);
echo totalBoxesRemoved($arr, $n);
// This code is contributed
// by shs
?>
Javascript
<script>
// Javascript program to find the number of
// boxes to be removed
// Function to find the number of
// boxes to be removed
function totalBoxesRemoved(arr, n)
{
var count = 0;
// Store height of previous pile
var prev = arr[0];
// Start traversing the array
for (var i = 1; i < n; i++) {
// if height of current pile is greater
// than previous pile
if (arr[i] > prev) {
// Increment count by difference
// of two heights
count += (arr[i] - prev);
// Update current height
arr[i] = prev;
// Update prev for next iteration
prev = arr[i];
}
else {
// Update prev for next iteration
prev = arr[i];
}
}
return count;
}
// Driver code
var arr = [5, 4, 7, 3, 2, 1 ];
var n = arr.length;
document.write( totalBoxesRemoved(arr, n));
</script>
3
Complejidad temporal : O(N), donde N es el número total de pilas.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shashank_Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA