Dada una array de enteros, la tarea es encontrar la máxima diferencia absoluta entre el elemento más pequeño de la izquierda y la derecha de cada elemento de la array.
Nota: Si no hay un elemento más pequeño en el lado derecho o izquierdo de cualquier elemento, tomamos cero como el elemento más pequeño. Por ejemplo, para el elemento más a la izquierda, el elemento más pequeño más cercano en el lado izquierdo se considera como 0. De manera similar, para los elementos más a la derecha, el elemento más pequeño en el lado derecho se considera como 0.
Ejemplos:
Input : arr[] = {2, 1, 8}
Output : 1
Left smaller LS[] {0, 0, 1}
Right smaller RS[] {1, 0, 0}
Maximum Diff of abs(LS[i] - RS[i]) = 1
Input : arr[] = {2, 4, 8, 7, 7, 9, 3}
Output : 4
Left smaller LS[] = {0, 2, 4, 4, 4, 7, 2}
Right smaller RS[] = {0, 3, 7, 3, 3, 3, 0}
Maximum Diff of abs(LS[i] - RS[i]) = 7 - 3 = 4
Input : arr[] = {5, 1, 9, 2, 5, 1, 7}
Output : 1
Una solución simple es encontrar los elementos más pequeños izquierdo y derecho más cercanos para cada elemento y luego actualizar la diferencia máxima entre el elemento más pequeño izquierdo y derecho, esto lleva O (n ^ 2) tiempo.
Una solución eficiente toma O(n) tiempo. Usamos una pila . La idea se basa en el enfoque discutido en el siguiente artículo de elemento mayor . La parte interesante aquí es que calculamos tanto a la izquierda como a la derecha usando la misma función.
Let input array be 'arr[]' and size of array be 'n'
Find all smaller element on left side
1. Create a new empty stack S and an array LS[]
2. For every element 'arr[i]' in the input arr[],
where 'i' goes from 0 to n-1.
a) while S is nonempty and the top element of
S is greater than or equal to 'arr[i]':
pop S
b) if S is empty:
'arr[i]' has no preceding smaller value
LS[i] = 0
c) else:
the nearest smaller value to 'arr[i]' is top
of stack
LS[i] = s.top()
d) push 'arr[i]' onto S
Find all smaller element on right side
3. First reverse array arr[]. After reversing the array,
right smaller become left smaller.
4. Create an array RRS[] and repeat steps 1 and 2 to
fill RRS (in-place of LS).
5. Initialize result as -1 and do following for every element
arr[i]. In the reversed array right smaller for arr[i] is
stored at RRS[n-i-1]
return result = max(result, LS[i]-RRS[n-i-1])
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find the difference b/w left and
// right smaller element of every element in array
#include<bits/stdc++.h>
using namespace std;
// Function to fill left smaller element for every
// element of arr[0..n-1]. These values are filled
// in SE[0..n-1]
void leftSmaller(int arr[], int n, int SE[])
{
// Create an empty stack
stack<int>S;
// Traverse all array elements
// compute nearest smaller elements of every element
for (int i=0; i<n; i++)
{
// Keep removing top element from S while the top
// element is greater than or equal to arr[i]
while (!S.empty() && S.top() >= arr[i])
S.pop();
// Store the smaller element of current element
if (!S.empty())
SE[i] = S.top();
// If all elements in S were greater than arr[i]
else
SE[i] = 0;
// Push this element
S.push(arr[i]);
}
}
// Function returns maximum difference b/w Left &
// right smaller element
int findMaxDiff(int arr[], int n)
{
int LS[n]; // To store left smaller elements
// find left smaller element of every element
leftSmaller(arr, n, LS);
// find right smaller element of every element
// first reverse the array and do the same process
int RRS[n]; // To store right smaller elements in
// reverse array
reverse(arr, arr + n);
leftSmaller(arr, n, RRS);
// find maximum absolute difference b/w LS & RRS
// In the reversed array right smaller for arr[i] is
// stored at RRS[n-i-1]
int result = -1;
for (int i=0 ; i< n ; i++)
result = max(result, abs(LS[i] - RRS[n-1-i]));
// return maximum difference b/w LS & RRS
return result;
}
// Driver program
int main()
{
int arr[] = {2, 4, 8, 7, 7, 9, 3};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Maximum diff : "
<< findMaxDiff(arr, n) << endl;
return 0;
}
Java
// Java program to find the difference b/w left and
// right smaller element of every element in array
import java.util.*;
class GFG
{
// Function to fill left smaller element for every
// element of arr[0..n-1]. These values are filled
// in SE[0..n-1]
static void leftSmaller(int arr[], int n, int SE[])
{
// Create an empty stack
Stack<Integer> S = new Stack<>();
// Traverse all array elements
// compute nearest smaller elements of every element
for (int i = 0; i < n; i++)
{
// Keep removing top element from S while the top
// element is greater than or equal to arr[i]
while (!S.empty() && S.peek() >= arr[i])
{
S.pop();
}
// Store the smaller element of current element
if (!S.empty())
{
SE[i] = S.peek();
}
// If all elements in S were greater than arr[i]
else
{
SE[i] = 0;
}
// Push this element
S.push(arr[i]);
}
}
// Function returns maximum difference b/w Left &
// right smaller element
static int findMaxDiff(int arr[], int n)
{
int[] LS = new int[n]; // To store left smaller elements
// find left smaller element of every element
leftSmaller(arr, n, LS);
// find right smaller element of every element
// first reverse the array and do the same process
int[] RRS = new int[n]; // To store right smaller elements in
// reverse array
reverse(arr);
leftSmaller(arr, n, RRS);
// find maximum absolute difference b/w LS & RRS
// In the reversed array right smaller for arr[i] is
// stored at RRS[n-i-1]
int result = -1;
for (int i = 0; i < n; i++)
{
result = Math.max(result, Math.abs(LS[i] - RRS[n - 1 - i]));
}
// return maximum difference b/w LS & RRS
return result;
}
static void reverse(int a[])
{
int i, k, n = a.length;
int t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
// Driver code
public static void main(String args[])
{
int arr[] = {2, 4, 8, 7, 7, 9, 3};
int n = arr.length;
System.out.println("Maximum diff : "
+ findMaxDiff(arr, n));
}
}
// This code is contributed by Princi Singh
Python3
# Python program to find the difference b/w left and # right smaller element of every element in the array # Function to fill left smaller element for every # element of arr[0..n-1]. These values are filled # in SE[0..n-1] def leftsmaller(arr, n, SE): # create an empty stack sta = [] # Traverse all array elements # compute nearest smaller elements of every element for i in range(n): # Keep removing top element from S while the top # element is greater than or equal to arr[i] while(sta != [] and sta[len(sta)-1] >= arr[i]): sta.pop() # Store the smaller element of current element if(sta != []): SE[i]=sta[len(sta)-1] # If all elements in S were greater than arr[i] else: SE[i]=0 # push this element sta.append(arr[i]) # Function returns maximum difference b/w Left & # right smaller element def findMaxDiff(arr, n): ls=[0]*n # to store left smaller elements rs=[0]*n # to store right smaller elements # find left smaller elements of every element leftsmaller(arr, n, ls) # find right smaller element of every element # by sending reverse of array leftsmaller(arr[::-1], n, rs) # find maximum absolute difference b/w LS & RRS # In the reversed array right smaller for arr[i] is # stored at RRS[n-i-1] res = -1 for i in range(n): res = max(res, abs(ls[i] - rs[n-1-i])) # return maximum difference b/w LS & RRS return res # Driver Program if __name__=='__main__': arr = [2, 4, 8, 7, 7, 9, 3] print "Maximum Diff :", findMaxDiff(arr, len(arr)) #Contributed By: Harshit Sidhwa
C#
// C# program to find the difference b/w left and
// right smaller element of every element in array
using System;
using System.Collections.Generic;
class GFG
{
// Function to fill left smaller element for every
// element of arr[0..n-1]. These values are filled
// in SE[0..n-1]
static void leftSmaller(int []arr, int n, int []SE)
{
// Create an empty stack
Stack<int> S = new Stack<int>();
// Traverse all array elements
// compute nearest smaller elements of every element
for (int i = 0; i < n; i++)
{
// Keep removing top element from S while the top
// element is greater than or equal to arr[i]
while (S.Count != 0 && S.Peek() >= arr[i])
{
S.Pop();
}
// Store the smaller element of current element
if (S.Count != 0)
{
SE[i] = S.Peek();
}
// If all elements in S were greater than arr[i]
else
{
SE[i] = 0;
}
// Push this element
S.Push(arr[i]);
}
}
// Function returns maximum difference b/w Left &
// right smaller element
static int findMaxDiff(int []arr, int n)
{
int[] LS = new int[n]; // To store left smaller elements
// find left smaller element of every element
leftSmaller(arr, n, LS);
// find right smaller element of every element
// first reverse the array and do the same process
int[] RRS = new int[n]; // To store right smaller elements in
// reverse array
reverse(arr);
leftSmaller(arr, n, RRS);
// find maximum absolute difference b/w LS & RRS
// In the reversed array right smaller for arr[i] is
// stored at RRS[n-i-1]
int result = -1;
for (int i = 0; i < n; i++)
{
result = Math.Max(result, Math.Abs(LS[i] -
RRS[n - 1 - i]));
}
// return maximum difference b/w LS & RRS
return result;
}
static void reverse(int[] a)
{
int i, k, n = a.Length;
int t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
// Driver code
public static void Main(String []args)
{
int []arr = {2, 4, 8, 7, 7, 9, 3};
int n = arr.Length;
Console.WriteLine("Maximum diff : " +
findMaxDiff(arr, n));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// Function to fill left smaller
// element for every element of
// arr[0..n-1]. These values are
// filled in SE[0..n-1]
function leftSmaller(&$arr, $n, &$SE)
{
$S = array();
// Traverse all array elements
// compute nearest smaller
// elements of every element
for ($i = 0; $i < $n; $i++)
{
// Keep removing top element
// from S while the top element
// is greater than or equal to arr[i]
while (!empty($S) && max($S) >= $arr[$i])
array_pop($S);
// Store the smaller element
// of current element
if (!empty($S))
$SE[$i] = max($S);
// If all elements in S were
// greater than arr[i]
else
$SE[$i] = 0;
// Push this element
array_push($S, $arr[$i]);
}
}
// Function returns maximum
// difference b/w Left &
// right smaller element
function findMaxDiff(&$arr, $n)
{
// To store left smaller elements
$LS = array_fill(0, $n, NULL);
// find left smaller element
// of every element
leftSmaller($arr, $n, $LS);
// find right smaller element
// of every element first reverse
// the array and do the same process
// To store right smaller
// elements in reverse array
$RRS = array_fill(0, $n, NULL);
$k = 0;
for($i = $n - 1; $i >= 0; $i--)
$x[$k++] = $arr[$i];
leftSmaller($x, $n, $RRS);
// find maximum absolute difference
// b/w LS & RRS. In the reversed
// array right smaller for arr[i]
// is stored at RRS[n-i-1]
$result = -1;
for ($i = 0 ; $i < $n ; $i++)
$result = max($result, abs($LS[$i] -
$RRS[$n - 1 - $i]));
// return maximum difference
// b/w LS & RRS
return $result;
}
// Driver Code
$arr = array(2, 4, 8, 7, 7, 9, 3);
$n = sizeof($arr);
echo "Maximum diff : " .
findMaxDiff($arr, $n) . "\n";
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to find the difference b/w left and
// right smaller element of every element in array
// Function to fill left smaller element for every
// element of arr[0..n-1]. These values are filled
// in SE[0..n-1]
function leftSmaller(arr,n,SE)
{
// Create an empty stack
let S=[]
// Traverse all array elements
// compute nearest smaller elements of every element
for (let i = 0; i < n; i++)
{
// Keep removing top element from S while the top
// element is greater than or equal to arr[i]
while (S.length!=0 && S[S.length-1] >= arr[i])
{
S.pop();
}
// Store the smaller element of current element
if (S.length!=0)
{
SE[i] = S[S.length-1];
}
// If all elements in S were greater than arr[i]
else
{
SE[i] = 0;
}
// Push this element
S.push(arr[i]);
}
}
// Function returns maximum difference b/w Left &
// right smaller element
function findMaxDiff(arr,n)
{
// To store left smaller elements
let LS = new Array(n);
for(let i=0;i<n;i++)
{
LS[i]=0;
}
// find left smaller element of every element
leftSmaller(arr, n, LS);
// find right smaller element of every element
// first reverse the array and do the same process
let RRS = new Array(n); // To store right smaller elements in
for(let i=0;i<n;i++)
{
RRS[i]=0;
}
// reverse array
reverse(arr);
leftSmaller(arr, n, RRS);
// find maximum absolute difference b/w LS & RRS
// In the reversed array right smaller for arr[i] is
// stored at RRS[n-i-1]
let result = -1;
for (let i = 0; i < n; i++)
{
result = Math.max(result, Math.abs(LS[i] - RRS[n - 1 - i]));
}
// return maximum difference b/w LS & RRS
return result;
}
function reverse(a)
{
let i, k, n = a.length;
let t;
for (i = 0; i < Math.floor(n / 2); i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
// Driver code
let arr=[2, 4, 8, 7, 7, 9, 3];
let n = arr.length;
document.write("Maximum diff : "
+ findMaxDiff(arr, n));
// This code is contributed by rag2127
</script>
Producción
Maximum diff : 4
Complejidad temporal: O(n)
Espacio auxiliar: O(n).
Este artículo es una contribución de Nishant_singh(pintu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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