Dada una array de elementos distintos, encuentre el elemento mayor anterior para cada elemento. Si el elemento mayor anterior no existe, imprima -1.
Ejemplos:
Input : arr[] = {10, 4, 2, 20, 40, 12, 30}
Output : -1, 10, 4, -1, -1, 40, 40
Input : arr[] = {10, 20, 30, 40}
Output : -1, -1, -1, -1
Input : arr[] = {40, 30, 20, 10}
Output : -1, 40, 30, 20
Complejidad de tiempo esperada : O(n)
Una solución simple es ejecutar dos bucles anidados. El bucle exterior elige un elemento uno por uno. El bucle interior, encuentra el elemento anterior que es mayor.
C++
// C++ program previous greater element
// A naive solution to print previous greater
// element for every element in an array.
#include <bits/stdc++.h>
using namespace std;
void prevGreater(int arr[], int n)
{
// Previous greater for first element never
// exists, so we print -1.
cout << "-1, ";
// Let us process remaining elements.
for (int i = 1; i < n; i++) {
// Find first element on left side
// that is greater than arr[i].
int j;
for (j = i-1; j >= 0; j--) {
if (arr[i] < arr[j]) {
cout << arr[j] << ", ";
break;
}
}
// If all elements on left are smaller.
if (j == -1)
cout << "-1, ";
}
}
// Driver code
int main()
{
int arr[] = { 10, 4, 2, 20, 40, 12, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
prevGreater(arr, n);
return 0;
}
Java
// Java program previous greater element
// A naive solution to print
// previous greater element
// for every element in an array.
import java.io.*;
import java.util.*;
import java.lang.*;
class GFG
{
static void prevGreater(int arr[],
int n)
{
// Previous greater for
// first element never
// exists, so we print -1.
System.out.print("-1, ");
// Let us process
// remaining elements.
for (int i = 1; i < n; i++)
{
// Find first element on
// left side that is
// greater than arr[i].
int j;
for (j = i-1; j >= 0; j--)
{
if (arr[i] < arr[j])
{
System.out.print(arr[j] + ", ");
break;
}
}
// If all elements on
// left are smaller.
if (j == -1)
System.out.print("-1, ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {10, 4, 2, 20, 40, 12, 30};
int n = arr.length;
prevGreater(arr, n);
}
}
Python 3
# Python 3 program previous greater element
# A naive solution to print previous greater
# element for every element in an array.
def prevGreater(arr, n) :
# Previous greater for first element never
# exists, so we print -1.
print("-1",end = ", ")
# Let us process remaining elements.
for i in range(1, n) :
flag = 0
# Find first element on left side
# that is greater than arr[i].
for j in range(i-1, -1, -1) :
if arr[i] < arr[j] :
print(arr[j],end = ", ")
flag = 1
break
# If all elements on left are smaller.
if j == 0 and flag == 0:
print("-1",end = ", ")
# Driver code
if __name__ == "__main__" :
arr = [10, 4, 2, 20, 40, 12, 30]
n = len(arr)
prevGreater(arr, n)
# This code is contributed by ANKITRAI1
C#
// C# program previous greater element
// A naive solution to print
// previous greater element
// for every element in an array.
using System;
class GFG
{
static void prevGreater(int[] arr,
int n)
{
// Previous greater for
// first element never
// exists, so we print -1.
Console.Write("-1, ");
// Let us process
// remaining elements.
for (int i = 1; i < n; i++)
{
// Find first element on
// left side that is
// greater than arr[i].
int j;
for (j = i-1; j >= 0; j--)
{
if (arr[i] < arr[j])
{
Console.Write(arr[j] + ", ");
break;
}
}
// If all elements on
// left are smaller.
if (j == -1)
Console.Write("-1, ");
}
}
// Driver Code
public static void Main()
{
int[] arr = {10, 4, 2, 20, 40, 12, 30};
int n = arr.Length;
prevGreater(arr, n);
}
}
PHP
<?php
// php program previous greater element
// A naive solution to print previous greater
// element for every element in an array.
function prevGreater(&$arr,$n)
{
// Previous greater for first element never
// exists, so we print -1.
echo( "-1, ");
// Let us process remaining elements.
for ($i = 1; $i < $n; $i++)
{
// Find first element on left side
// that is greater than arr[i].
for ($j = $i-1; $j >= 0; $j--)
{
if ($arr[$i] < $arr[$j])
{
echo($arr[$j]);
echo( ", ");
break;
}
}
// If all elements on left are smaller.
if ($j == -1)
echo("-1, ");
}
}
// Driver code
$arr = array(10, 4, 2, 20, 40, 12, 30);
$n = sizeof($arr) ;
prevGreater($arr, $n);
//This code is contributed by Shivi_Aggarwal.
?>
Javascript
<script>
// Javascript program previous greater element
// A naive solution to print
// previous greater element
// for every element in an array.
function prevGreater(arr,n)
{
// Previous greater for
// first element never
// exists, so we print -1.
document.write("-1, ");
// Let us process
// remaining elements.
for (let i = 1; i < n; i++)
{
// Find first element on
// left side that is
// greater than arr[i].
let j;
for (j = i-1; j >= 0; j--)
{
if (arr[i] < arr[j])
{
document.write(arr[j] + ", ");
break;
}
}
// If all elements on
// left are smaller.
if (j == -1)
document.write("-1, ");
}
}
// Driver Code
let arr=[10, 4, 2, 20, 40, 12, 30];
let n = arr.length;
prevGreater(arr, n);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
-1, 10, 4, -1, -1, 40, 40
Una solución eficiente es utilizar la estructura de datos de pila . Si miramos más de cerca, podemos notar que este problema es una variación del problema de stock span . Mantenemos el elemento mayor anterior en una pila.
C++
// C++ program previous greater element
// An efficient solution to print previous greater
// element for every element in an array.
#include <bits/stdc++.h>
using namespace std;
void prevGreater(int arr[], int n)
{
// Create a stack and push index of first element
// to it
stack<int> s;
s.push(arr[0]);
// Previous greater for first element is always -1.
cout << "-1, ";
// Traverse remaining elements
for (int i = 1; i < n; i++) {
// Pop elements from stack while stack is not empty
// and top of stack is smaller than arr[i]. We
// always have elements in decreasing order in a
// stack.
while (s.empty() == false && s.top() < arr[i])
s.pop();
// If stack becomes empty, then no element is greater
// on left side. Else top of stack is previous
// greater.
s.empty() ? cout << "-1, " : cout << s.top() << ", ";
s.push(arr[i]);
}
}
// Driver code
int main()
{
int arr[] = { 10, 4, 2, 20, 40, 12, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
prevGreater(arr, n);
return 0;
}
Java
// Java program previous greater element
// An efficient solution to
// print previous greater
// element for every element
// in an array.
import java.io.*;
import java.util.*;
import java.lang.*;
class GFG
{
static void prevGreater(int arr[],
int n)
{
// Create a stack and push
// index of first element
// to it
Stack<Integer> s = new Stack<Integer>();
s.push(arr[0]);
// Previous greater for
// first element is always -1.
System.out.print("-1, ");
// Traverse remaining elements
for (int i = 1; i < n; i++)
{
// Pop elements from stack
// while stack is not empty
// and top of stack is smaller
// than arr[i]. We always have
// elements in decreasing order
// in a stack.
while (s.empty() == false &&
s.peek() < arr[i])
s.pop();
// If stack becomes empty, then
// no element is greater on left
// side. Else top of stack is
// previous greater.
if (s.empty() == true)
System.out.print("-1, ");
else
System.out.print(s.peek() + ", ");
s.push(arr[i]);
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 10, 4, 2, 20, 40, 12, 30 };
int n = arr.length;
prevGreater(arr, n);
}
}
Python3
# Python3 program to print previous greater element
# An efficient solution to print previous greater
# element for every element in an array.
import math as mt
def prevGreater(arr, n):
# Create a stack and push index of
# first element to it
s = list();
s.append(arr[0])
# Previous greater for first element
# is always -1.
print("-1, ", end = "")
# Traverse remaining elements
for i in range(1, n):
# Pop elements from stack while stack is
# not empty and top of stack is smaller
# than arr[i]. We always have elements in
# decreasing order in a stack.
while (len(s) > 0 and s[-1] < arr[i]):
s.pop()
# If stack becomes empty, then no element
# is greater on left side. Else top of stack
# is previous greater.
if len(s) == 0:
print("-1, ", end = "")
else:
print(s[-1], ", ", end = "")
s.append(arr[i])
# Driver code
arr = [ 10, 4, 2, 20, 40, 12, 30 ]
n = len(arr)
prevGreater(arr, n)
# This code is contributed by
# mohit kumar 29
C#
// C# program previous greater element
// An efficient solution to
// print previous greater
// element for every element
// in an array.
using System;
using System.Collections.Generic;
class GFG
{
static void prevGreater(int []arr,
int n)
{
// Create a stack and push
// index of first element
// to it
Stack<int> s = new Stack<int>();
s.Push(arr[0]);
// Previous greater for
// first element is always -1.
Console.Write("-1, ");
// Traverse remaining elements
for (int i = 1; i < n; i++)
{
// Pop elements from stack
// while stack is not empty
// and top of stack is smaller
// than arr[i]. We always have
// elements in decreasing order
// in a stack.
while (s.Count != 0 &&
s.Peek() < arr[i])
s.Pop();
// If stack becomes empty, then
// no element is greater on left
// side. Else top of stack is
// previous greater.
if (s.Count == 0)
Console.Write("-1, ");
else
Console.Write(s.Peek() + ", ");
s.Push(arr[i]);
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 10, 4, 2, 20, 40, 12, 30 };
int n = arr.Length;
prevGreater(arr, n);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program previous greater element
// An efficient solution to
// print previous greater
// element for every element
// in an array.
function prevGreater(arr,n)
{
// Create a stack and push
// index of first element
// to it
let s = [];
s.push(arr[0]);
// Previous greater for
// first element is always -1.
document.write("-1, ");
// Traverse remaining elements
for (let i = 1; i < n; i++)
{
// Pop elements from stack
// while stack is not empty
// and top of stack is smaller
// than arr[i]. We always have
// elements in decreasing order
// in a stack.
while (s.length!=0 &&
s[s.length-1] < arr[i])
s.pop();
// If stack becomes empty, then
// no element is greater on left
// side. Else top of stack is
// previous greater.
if (s.length==0)
document.write("-1, ");
else
document.write(s[s.length-1] + ", ");
s.push(arr[i]);
}
}
// Driver Code
let arr=[10, 4, 2, 20, 40, 12, 30];
let n = arr.length;
prevGreater(arr, n);
// This code is contributed by rag2127
</script>
Producción:
-1, 10, 4, -1, -1, 40, 40
Complejidad temporal: O(n). Parece más que O(n) a primera vista. Si observamos más de cerca, podemos observar que cada elemento de la array se agrega y elimina de la pila como máximo una vez. Así que hay un total de 2n operaciones como máximo. Suponiendo que una operación de pila requiere un tiempo O(1), podemos decir que la complejidad del tiempo es O(n).
Espacio auxiliar: O(n) en el peor de los casos cuando todos los elementos se ordenan en orden decreciente.