Dada una array arr[] que contiene N enteros positivos. La tarea es encontrar todos los elementos que son más pequeños que todos los elementos a su derecha.
Ejemplos:
Entrada: arr[] = {6, 14, 13, 21, 17, 19}
Salida: [6, 13, 17, 19]
Explicación: Todos los elementos de la salida siguen la condición.Entrada: arr[] = {10, 3, 4, 8, 7}
Salida: [3, 4, 7]
Enfoque ingenuo: este enfoque utiliza dos bucles. Para cada elemento, recorra la array a su derecha y verifique si existe algún elemento más pequeño o no. Si todos los elementos en la parte derecha de la array son mayores que ella, imprima este elemento.
Complejidad temporal: O(N*N)
Espacio auxiliar: O(1)
Enfoque eficiente: en el enfoque eficiente, la idea es usar un Stack . Siga los pasos que se mencionan a continuación:
- Iterar la array desde el principio de la array.
- Para cada elemento de la array, extraiga todos los elementos presentes en la pila que sean mayores que él y luego introdúzcalos en la pila.
- Si ningún elemento es mayor que él, entonces el elemento actual es una respuesta.
- Por último, la pila permanece con elementos que son más pequeños que todos los elementos presentes a su derecha.
A continuación se muestra la implementación del código del enfoque anterior.
C++
// C++ program to find all elements in array
// that are smaller than all elements
// to their right.
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
// Function to print all elements which are
// smaller than all elements present
// to their right
void FindDesiredElements(vector<int> const& arr)
{
// Create an empty stack
stack<int> stk;
// Do for each element
for (int i : arr) {
// Pop all the elements that
// are greater than the
// current element
while (!stk.empty() && stk.top() > i) {
stk.pop();
}
// Push current element into the stack
stk.push(i);
}
// Print all elements in the stack
while (!stk.empty()) {
cout << stk.top() << " ";
stk.pop();
}
}
// Driver Code
int main()
{
vector<int> arr = { 6, 14, 13, 21, 17, 19 };
FindDesiredElements(arr);
return 0;
}
Java
// Java program to find all elements in array
// that are smaller than all elements
// to their right.
import java.util.ArrayList;
import java.util.Stack;
class GFG {
// Function to print all elements which are
// smaller than all elements present
// to their right
static void FindDesiredElements(ArrayList<Integer> arr)
{
// Create an empty stack
Stack<Integer> stk = new Stack<Integer>();
// Do for each element
for (int i : arr)
{
// Pop all the elements that
// are greater than the
// current element
while (!stk.empty() && stk.peek() > i) {
stk.pop();
}
// Push current element into the stack
stk.push(i);
}
// Print all elements in the stack
while (!stk.empty()) {
System.out.print(stk.peek() + " ");
stk.pop();
}
}
// Driver Code
public static void main(String args[])
{
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(6);
arr.add(14);
arr.add(13);
arr.add(21);
arr.add(17);
arr.add(19);
FindDesiredElements(arr);
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# python program to find all elements in array # that are smaller than all elements # to their right. # Function to print all elements which are # smaller than all elements present # to their right def FindDesiredElements(arr): # Create an empty stack stk = [] # Do for each element for i in arr : # Pop all the elements that # are greater than the # current element while (len(stk)!=0 and stk[len(stk)-1] > i): stk.pop() # Push current element into the stack stk.append(i) # Print all elements in the stack while (len(stk) != 0): print(stk[len(stk)-1],end = " ") stk.pop() # Driver Code arr = [] arr.append(6) arr.append(14) arr.append(13) arr.append(21) arr.append(17) arr.append(19) FindDesiredElements(arr) # This code is contributed by shinjanpatra
C#
// C# program to find all elements in array
// that are smaller than all elements
// to their right.
using System;
using System.Collections.Generic;
public class GFG {
// Function to print all elements which are
// smaller than all elements present
// to their right
static void FindDesiredElements(List<int> arr) {
// Create an empty stack
Stack<int> stk = new Stack<int>();
// Do for each element
foreach (int i in arr) {
// Pop all the elements that
// are greater than the
// current element
while (stk.Count!=0 && stk.Peek() > i) {
stk.Pop();
}
// Push current element into the stack
stk.Push(i);
}
// Print all elements in the stack
while (stk.Count>0) {
Console.Write(stk.Peek() + " ");
stk.Pop();
}
}
// Driver Code
public static void Main(String []args) {
List<int> arr = new List<int>();
arr.Add(6);
arr.Add(14);
arr.Add(13);
arr.Add(21);
arr.Add(17);
arr.Add(19);
FindDesiredElements(arr);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program to find all elements in array
// that are smaller than all elements
// to their right.
// Function to print all elements which are
// smaller than all elements present
// to their right
function FindDesiredElements( arr) {
// Create an empty stack
var stk = [];
// Do for each element
for (var i of arr) {
// Pop all the elements that
// are greater than the
// current element
while (stk.length!=0 && stk[stk.length-1] > i) {
stk.pop();
}
// Push current element into the stack
stk.push(i);
}
// Print all elements in the stack
while (stk.length != 0) {
document.write(stk[stk.length-1] + " ");
stk.pop();
}
}
// Driver Code
var arr = [];
arr.push(6);
arr.push(14);
arr.push(13);
arr.push(21);
arr.push(17);
arr.push(19);
FindDesiredElements(arr);
// This code is contributed by Rajput-Ji
</script>
Producción
19 17 13 6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque de espacio optimizado: la idea es recorrer la array de derecha a izquierda (orden inverso) y mantener una variable auxiliar que almacene el elemento mínimo encontrado hasta el momento. Este enfoque descuidará el uso de stack. Siga los pasos a continuación:
- Comience a iterar desde el final de la array.
- Si el elemento actual es más pequeño que el mínimo hasta el momento, entonces se encuentra el elemento. Actualice el valor que almacena el valor mínimo hasta el momento. Imprime todos esos valores como la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to print all elements which are
// smaller than all elements present to their right
#include <iostream>
#include <limits.h>
using namespace std;
// Function to print all elements which are
// smaller than all elements
// present to their right
void FindDesiredElements(int arr[], int n)
{
int min_so_far = INT_MAX;
// Traverse the array from right to left
for (int j = n - 1; j >= 0; j--) {
// If the current element is greater
// than the maximum so far, print it
// and update `max_so_far`
if (arr[j] <= min_so_far) {
min_so_far = arr[j];
cout << arr[j] << " ";
}
}
}
// Driver Code
int main()
{
int arr[] = { 6, 14, 13, 21, 17, 19 };
int N = sizeof(arr) / sizeof(arr[0]);
FindDesiredElements(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to print all elements which are
// smaller than all elements
// present to their right
static void FindDesiredElements(int[] arr, int n)
{
int min_so_far = Integer.MAX_VALUE;
// Traverse the array from right to left
for (int j = n - 1; j >= 0; j--)
{
// If the current element is greater
// than the maximum so far, print it
// and update `max_so_far`
if (arr[j] <= min_so_far) {
min_so_far = arr[j];
System.out.print(arr[j] + " ");
}
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 6, 14, 13, 21, 17, 19 };
int N = arr.length;
FindDesiredElements(arr, N);
}
}
// This code is contributed by code_hunt.
Python3
# Python code for the above approach # Function to print all elements which are # smaller than all elements # present to their right def FindDesiredElements(arr, n): min_so_far = 10 ** 9; # Traverse the array from right to left for j in range(n - 1, -1, -1): # If the current element is greater # than the maximum so far, print it # and update `max_so_far` if (arr[j] <= min_so_far): min_so_far = arr[j]; print(arr[j], end=" ") # Driver Code arr = [6, 14, 13, 21, 17, 19]; N = len(arr) FindDesiredElements(arr, N); # This code is contributed by Saurabh Jaiswal
C#
// C# program to print all elements which are
// smaller than all elements present to their right
using System;
class GFG {
// Function to print all elements which are
// smaller than all elements
// present to their right
static void FindDesiredElements(int[] arr, int n)
{
int min_so_far = Int32.MaxValue;
// Traverse the array from right to left
for (int j = n - 1; j >= 0; j--) {
// If the current element is greater
// than the maximum so far, print it
// and update `max_so_far`
if (arr[j] <= min_so_far) {
min_so_far = arr[j];
Console.Write(arr[j] + " ");
}
}
}
// Driver Code
public static void Main()
{
int[] arr = { 6, 14, 13, 21, 17, 19 };
int N = arr.Length;
FindDesiredElements(arr, N);
}
}
Javascript
<script>
// JavaScript code for the above approach
// Function to print all elements which are
// smaller than all elements
// present to their right
function FindDesiredElements(arr, n)
{
let min_so_far = Number.MAX_VALUE;
// Traverse the array from right to left
for (let j = n - 1; j >= 0; j--)
{
// If the current element is greater
// than the maximum so far, print it
// and update `max_so_far`
if (arr[j] <= min_so_far) {
min_so_far = arr[j];
document.write(arr[j] + " ");
}
}
}
// Driver Code
let arr = [6, 14, 13, 21, 17, 19];
let N = arr.length;
FindDesiredElements(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción
19 17 13 6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA