Dada una array arr[] de N enteros distintos, la tarea es calcular para cada índice i (1≤i≤N) un rango [L, R] tal que arr[i] = min(arr[L], arr[ L+1], … arr[R]) , donde L≤i≤R y RL se maximizan.
Ejemplos:
Entrada: N = 3, arr[] = {1, 3, 2}
Salida: 1 3
2 2
2 3
Explicación: 1 es el mínimo en el rango [1, 3]
3 es el mínimo en el rango [2, 2]
2 es mínimo en el rango [2, 3]Entrada: N = 3, arr[] = {4, 5, 6}
Salida: 1 3
2 3
3 3
Enfoque: se puede observar que se requieren elementos anteriores más pequeños y siguientes más pequeños en cada índice para calcular el rango requerido. La idea es usar pilas para encontrar los elementos mayores anteriores y siguientes. Siga los pasos a continuación para resolver el problema:
- Cree dos arrays , L[] y R[] , para almacenar el elemento más pequeño más cercano a la izquierda y el elemento más pequeño más cercano a la derecha del elemento actual, respectivamente.
- Cree una pila S y agregue el índice del primer elemento en ella.
- Atraviese la array dada , arr[] y extraiga la pila hasta la parte superior de la pila , S no es más pequeño que el elemento actual.
- Ahora configure el elemento más pequeño más cercano a la izquierda, es decir , L[i] como la parte superior de S , y si S está vacío, configúrelo como 0. Empuje el elemento actual a S .
- Del mismo modo, recorra desde el final en la dirección opuesta y siga los mismos pasos para llenar la array, R[] .
- Iterar en el rango [1, N] e imprimir L[i] y R[i] para cada índice i .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the range for each index
void rangeFinder(int arr[], int N)
{
// Array to store index of closest smaller
// element at left sub-array
int L[N];
// Array to store index of closest smaller
// element at right sub-array
int R[N];
// Stack to find previous smaller element
stack<int> S;
// Since there is no element before first
// element, so set L[0]=0
L[0] = 0;
// Push the first element index in stack
S.push(0);
// Traverse the array, arr[]
for (int i = 1; i < N; i++) {
// Pop until the top of stack is greater
// than current element
while (!S.empty() && arr[S.top()] > arr[i])
S.pop();
// Update L[i] as peek as it is
// previous smaller element
if (!S.empty())
L[i] = S.top() + 1;
// Otherwise, update L[i] to 0
else
L[i] = 0;
// Push the current index
S.push(i);
}
// Empty the stack, S
while (!S.empty())
S.pop();
// Since there is no element after
// last element, so set R[N-1]=N-1
R[N - 1] = N - 1;
// Push the last element index into stack
S.push(N - 1);
// Traverse the array from the end
for (int i = N - 2; i >= 0; i--) {
// Pop until the top of S is greater
// than current element
while (!S.empty() && arr[S.top()] > arr[i])
S.pop();
// Set R[i] as top as it is previous
// smaller element from end
if (!S.empty())
R[i] = S.top() - 1;
// Otherwise, update R[i] as N-1
else
R[i] = N - 1;
// Push the current index
S.push(i);
}
// Print the required range using L and R array
for (int i = 0; i < N; i++) {
cout << L[i] + 1 << " " << R[i] + 1 << endl;
}
}
// Driver Code
int main()
{
// Given Input
int arr[] = { 1, 3, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
rangeFinder(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to print the range for each index
static void rangeFinder(int arr[], int N)
{
// Array to store index of closest smaller
// element at left sub-array
int[] L = new int[N];
// Array to store index of closest smaller
// element at right sub-array
int[] R = new int[N];
// Stack to find previous smaller element
Stack<Integer> S = new Stack<Integer>();
// Since there is no element before first
// element, so set L[0]=0
L[0] = 0;
// Push the first element index in stack
S.push(0);
// Traverse the array, arr[]
for(int i = 1; i < N; i++)
{
// Pop until the top of stack is greater
// than current element
while (!S.empty() && arr[S.peek()] > arr[i])
S.pop();
// Update L[i] as peek as it is
// previous smaller element
if (!S.empty())
L[i] = S.peek() + 1;
// Otherwise, update L[i] to 0
else
L[i] = 0;
// Push the current index
S.push(i);
}
// Empty the stack, S
while (!S.empty())
S.pop();
// Since there is no element after
// last element, so set R[N-1]=N-1
R[N - 1] = N - 1;
// Push the last element index into stack
S.push(N - 1);
// Traverse the array from the end
for(int i = N - 2; i >= 0; i--)
{
// Pop until the top of S is greater
// than current element
while (!S.empty() && arr[S.peek()] > arr[i])
S.pop();
// Set R[i] as top as it is previous
// smaller element from end
if (!S.empty())
R[i] = S.peek() - 1;
// Otherwise, update R[i] as N-1
else
R[i] = N - 1;
// Push the current index
S.push(i);
}
// Print the required range using L and R array
for(int i = 0; i < N; i++)
{
System.out.println((L[i] + 1) + " " +
(R[i] + 1));
}
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int arr[] = { 1, 3, 2 };
int N = arr.length;
// Function Call
rangeFinder(arr, N);
}
}
// This code is contributed by MuskanKalra1
Python3
# Python3 program for the above approach # Function to print the range for each index def rangeFinder(arr, N): # Array to store index of closest smaller # element at left sub-array L = [0 for i in range(N)] # Array to store index of closest smaller # element at right sub-array R = [0 for i in range(N)] # Stack to find previous smaller element S = [] # Since there is no element before first # element, so set L[0]=0 L[0] = 0 # Push the first element index in stack S.append(0) # Traverse the array, arr[] for i in range(1, N, 1): # Pop until the top of stack is greater # than current element while (len(S) > 0 and arr[S[len(S) - 1]] > arr[i]): S = S[:-1] # Update L[i] as peek as it is # previous smaller element if (len(S) > 0): L[i] = S[len(S) - 1] + 1 # Otherwise, update L[i] to 0 else: L[i] = 0 # Push the current index S.append(i) # Empty the stack, S while (len(S) > 0): S.pop() # Since there is no element after # last element, so set R[N-1]=N-1 R[N - 1] = N - 1 # Push the last element index into stack S.append(N - 1) # Traverse the array from the end i = N - 2 while (i >= 0): # Pop until the top of S is greater # than current element while (len(S) > 0 and arr[S[len(S) - 1]] > arr[i]): S = S[:-1] # Set R[i] as top as it is previous # smaller element from end if (len(S) > 0): R[i] = S[len(S) - 1] - 1; # Otherwise, update R[i] as N-1 else: R[i] = N - 1 # Push the current index S.append(i) i -= 1 # Print the required range using L and R array for i in range(N): print(L[i] + 1, R[i] + 1) # Driver Code if __name__ == '__main__': # Given Input arr = [ 1, 3, 2 ] N = len(arr) # Function Call rangeFinder(arr, N) # This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG {
// Function to print the range for each index
static void rangeFinder(int[] arr, int N)
{
// Array to store index of closest smaller
// element at left sub-array
int[] L = new int[N];
// Array to store index of closest smaller
// element at right sub-array
int[] R = new int[N];
// Stack to find previous smaller element
Stack S = new Stack();
// Since there is no element before first
// element, so set L[0]=0
L[0] = 0;
// Push the first element index in stack
S.Push(0);
// Traverse the array, arr[]
for(int i = 1; i < N; i++)
{
// Pop until the top of stack is greater
// than current element
while (S.Count > 0 && arr[(int)S.Peek()] > arr[i])
S.Pop();
// Update L[i] as peek as it is
// previous smaller element
if (S.Count > 0)
L[i] = (int)S.Peek() + 1;
// Otherwise, update L[i] to 0
else
L[i] = 0;
// Push the current index
S.Push(i);
}
// Empty the stack, S
while (S.Count > 0)
S.Pop();
// Since there is no element after
// last element, so set R[N-1]=N-1
R[N - 1] = N - 1;
// Push the last element index into stack
S.Push(N - 1);
// Traverse the array from the end
for(int i = N - 2; i >= 0; i--)
{
// Pop until the top of S is greater
// than current element
while (S.Count > 0 && arr[(int)S.Peek()] > arr[i])
S.Pop();
// Set R[i] as top as it is previous
// smaller element from end
if (S.Count > 0)
R[i] = (int)S.Peek() - 1;
// Otherwise, update R[i] as N-1
else
R[i] = N - 1;
// Push the current index
S.Push(i);
}
// Print the required range using L and R array
for(int i = 0; i < N; i++)
{
Console.WriteLine((L[i] + 1) + " " + (R[i] + 1));
}
}
static void Main()
{
// Given Input
int[] arr = { 1, 3, 2 };
int N = arr.Length;
// Function Call
rangeFinder(arr, N);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// JavaScript program for the above approach
// Function to print the range for each index
function rangeFinder(arr, N) {
// Array to store index of closest smaller
// element at left sub-array
let L = new Array(N).fill(0);
// Array to store index of closest smaller
// element at right sub-array
let R = new Array(N).fill(0);
// Stack to find previous smaller element
let S = [];
// Since there is no element before first
// element, so set L[0]=0
L[0] = 0;
// Push the first element index in stack
S.push(0);
// Traverse the array, arr[]
for (let i = 1; i < N; i++) {
// Pop until the top of stack is greater
// than current element
while (S.length && arr[S[S.length - 1]] > arr[i])
S.pop();
// Update L[i] as peek as it is
// previous smaller element
if (S.length)
L[i] = S[S.length - 1] + 1;
// Otherwise, update L[i] to 0
else
L[i] = 0;
// Push the current index
S.push(i);
}
// Empty the stack, S
while (S.length)
S.pop();
// Since there is no element after
// last element, so set R[N-1]=N-1
R[N - 1] = N - 1;
// Push the last element index into stack
S.push(N - 1);
// Traverse the array from the end
for (let i = N - 2; i >= 0; i--) {
// Pop until the top of S is greater
// than current element
while (S.length && arr[S[S.length - 1]] > arr[i])
S.pop();
// Set R[i] as top as it is previous
// smaller element from end
if (S.length)
R[i] = S[S.length - 1] - 1;
// Otherwise, update R[i] as N-1
else
R[i] = N - 1;
// Push the current index
S.push(i);
}
// Print the required range using L and R array
for (let i = 0; i < N; i++) {
document.write(L[i] + 1 + " ")
document.write(R[i] + 1 + "<br>");
}
}
// Driver Code
// Given Input
let arr = [1, 3, 2];
let N = arr.length;
// Function Call
rangeFinder(arr, N);
</script>
Producción:
1 3 2 2 2 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA