Dado un arreglo arr[] de tamaño N , la tarea es calcular, para i(0<=i<N), la longitud máxima de un subarreglo que contiene arr[i], donde arr[i] es el elemento máximo.
Ejemplo:
Entrada: arr[ ] = {62, 97, 49, 59, 54, 92, 21}, N=7
Salida:
1 7 1 3 1 5 1
Explicación: La longitud máxima del subarreglo en el que el primer elemento de índice es máximo es 1 , el subarreglo que consta solo del primer elemento.
Para el segundo elemento, es decir, 97, longitud máxima del subarreglo = 7. Podemos observar que 97 es el elemento máximo en el arreglo A.
Para el tercer elemento, solo 49 pueden estar en el subarreglo. Por lo tanto, la longitud máxima posible = 1.
Para el cuarto elemento, el subarreglo [49, 59, 54] es posible donde 59 es el número máximo. Por lo tanto, longitud = 3.
Del mismo modo, calculamos para cada índice de la array.Entrada: arr[]={1, 4, 5, 2, 3}
Salida:
1 2 5 1 2
Enfoque ingenuo:
- Para cada índice ‘i’ , recorra ambos lados de la array hasta encontrar un elemento mayor que arr[i] .
- Cuente el número de elementos en el rango, que será la longitud máxima de un subarreglo en el que arr[i] es el elemento más grande.
Complejidad temporal: O(N 2 ),
Enfoque eficiente: la idea es usar la estructura de datos de la pila para calcular el siguiente elemento mayor para cada índice (una vez a la izquierda y otra a la derecha).
Por ejemplo,
Sea arr[]={1, 3, 1, 2, 1, 5}, para i=3 , el siguiente elemento mayor a la izquierda está en el índice 1
y a la derecha está en el índice 5 .
Por lo tanto, la longitud del subarreglo en el que es mayor es 5-1-1=3 , es decir, de los índices 2 a 4 o {1, 2, 1}
Siga los pasos a continuación para resolver el problema:
- Encuentre el índice del siguiente elemento mayor para cada índice y guárdelo en una array utilizando la estructura de datos de pila para cada i(0<=i<N).
- De manera similar, almacene el siguiente elemento mayor para cada índice en el lado izquierdo de la array.
- Recorra la array y para cada índice, i , imprima el número de elementos entre el siguiente elemento mayor en el lado izquierdo y el siguiente elemento mayor en el lado derecho.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to compute
// next greater element indices on the
// right side on any index
vector<int> rightGreaterElement(int arr[], int n)
{
// to store the elements of array arr
// with their index
vector<pair<int, int> > B(n);
for (int i = 0; i < n; i++) {
B[i].first = arr[i];
B[i].second = i;
}
// to store indices of next greater element
// on the right side
vector<int> vec(n, -1);
// to store the pairs
stack<pair<int, int> > st;
for (int i = 0; i < n; i++) {
// if the stack is empty,
// push the pair
if (st.empty()) {
st.push(B[i]);
}
else {
// Pop and assign till
// the top is smaller
while (!st.empty()
&& st.top().first < B[i].first) {
vec[st.top().second] = B[i].second;
st.pop();
}
st.push(B[i]);
}
}
// assign n to element
// having no next greater element
while (!st.empty()) {
vec[st.top().second] = n;
st.pop();
}
// return the vector
return vec;
}
// Function to compute next greater element
// indices on the left side on any index
vector<int> leftGreaterElement(int arr[], int n)
{
// store the elements of array arr
// with their index
vector<pair<int, int> > B(n);
for (int i = 0; i < n; i++) {
B[i].first = arr[i];
B[i].second = i;
}
// array to store indices of next
// greater element on the left side
vector<int> vec(n, -1);
// stack to store the pairs
stack<pair<int, int> > st;
for (int i = n - 1; i >= 0; i--) {
// if the stack is empty, push the pair
if (st.empty()) {
st.push(B[i]);
}
else {
// pop and assign till top is smaller
while (!st.empty()
&& st.top().first < B[i].first) {
vec[st.top().second] = B[i].second;
st.pop();
}
st.push(B[i]);
}
}
// assign -1 to element having
// no next greater element
while (!st.empty()) {
vec[st.top().second] = -1;
st.pop();
}
// returning the vector
// with indices of next greater
// elements on the left side.
return vec;
}
// Function to print the maximum
// length of subarrays for all
// indices where A[i] is the
// maximum element in the subarray
void maximumSubarrayLength(int arr[], int N)
{
// array having index of next
// greater element on the right side.
vector<int> right = rightGreaterElement(arr, N);
// array having index of next
// greater element on the left side.
vector<int> left = leftGreaterElement(arr, N);
// print the range between the
// next greater elements on both the sides.
for (int i = 0; i < N; i++) {
int l = left[i];
int r = right[i];
cout << r - l - 1 << " ";
}
}
// Driver code
int main()
{
// Input
int arr[] = { 62, 97, 49, 59, 54, 92, 21 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
maximumSubarrayLength(arr, N);
return 0;
}
Java
// Java code for the above approach
import java.util.*;
import java.awt.Point;
public class Main
{
// Function to compute
// next greater element indices on the
// right side on any index
static int[] rightGreaterElement(int[] arr, int n)
{
// to store the elements of array arr
// with their index
int[][] B = new int[n][2];
for (int i = 0; i < n; i++) {
B[i][0] = arr[i];
B[i][1] = i;
}
// to store indices of next greater element
// on the right side
int[] vec = new int[n];
Arrays.fill(vec, -1);
// to store the pairs
Stack<Point> st = new Stack<Point>();
for (int i = 0; i < n; i++) {
// if the stack is empty,
// push the pair
if (st.size() == 0) {
st.push(new Point(B[i][0], B[i][1]));
}
else {
// Pop and assign till
// the top is smaller
while (st.size() > 0 && (st.peek()).x < B[i][0]) {
vec[(st.peek()).y] = B[i][1];
st.pop();
}
st.push(new Point(B[i][0], B[i][1]));
}
}
// assign n to element
// having no next greater element
while (st.size() > 0) {
vec[(st.peek()).y] = n;
st.pop();
}
// return the vector
return vec;
}
// Function to compute next greater element
// indices on the left side on any index
static int[] leftGreaterElement(int[] arr, int n)
{
// store the elements of array arr
// with their index
int[][] B = new int[n][2];
for (int i = 0; i < n; i++) {
B[i][0] = arr[i];
B[i][1] = i;
}
// array to store indices of next
// greater element on the left side
int[] vec = new int[n];
Arrays.fill(vec, -1);
// stack to store the pairs
Stack<Point> st = new Stack<Point>();
for (int i = n - 1; i >= 0; i--) {
// if the stack is empty, push the pair
if (st.size() == 0) {
st.push(new Point(B[i][0], B[i][1]));
}
else {
// pop and assign till top is smaller
while (st.size() > 0 && (st.peek()).x < B[i][0]) {
vec[(st.peek()).y] = B[i][1];
st.pop();
}
st.push(new Point(B[i][0], B[i][1]));
}
}
// assign -1 to element having
// no next greater element
while (st.size() > 0) {
vec[(st.peek()).y] = -1;
st.pop();
}
// returning the vector
// with indices of next greater
// elements on the left side.
return vec;
}
// Function to print the maximum
// length of subarrays for all
// indices where A[i] is the
// maximum element in the subarray
static void maximumSubarrayLength(int[] arr, int N)
{
// array having index of next
// greater element on the right side.
int[] right = rightGreaterElement(arr, N);
// array having index of next
// greater element on the left side.
int[] left = leftGreaterElement(arr, N);
// print the range between the
// next greater elements on both the sides.
for (int i = 0; i < N; i++) {
int l = left[i];
int r = right[i];
System.out.print((r - l - 1) + " ");
}
}
public static void main(String[] args) {
// Input
int[] arr = { 62, 97, 49, 59, 54, 92, 21 };
int N = arr.length;
// Function call
maximumSubarrayLength(arr, N);
}
}
// This code is contributed by mukesh07.
Python3
# Python3 code for the above approach # Function to compute next greater # element indices on the right side # on any index def rightGreaterElement(arr, n): # To store the elements of array arr # with their index B = [[0, 0] for i in range(n)] for i in range(n): B[i][0] = arr[i] B[i][1] = i # To store indices of next greater element # on the right side vec = [-1 for i in range(n)] # To store the pairs st = [] for i in range(n): # If the stack is empty, # push the pair if (len(st) == 0): st.append(B[i]) else: # Pop and assign till # the top is smaller while (len(st) > 0 and st[-1][0] < B[i][0]): vec[st[-1][1]] = B[i][1] st.pop() st.append(B[i]) # Assign n to element # having no next greater element while (len(st) > 0): vec[st[-1][1]] = n st.pop() # Return the vector return vec # Function to compute next greater element # indices on the left side on any index def leftGreaterElement(arr, n): # Store the elements of array arr # with their index B = [[0,0] for i in range(n)] for i in range(n): B[i][0] = arr[i] B[i][1] = i # Array to store indices of next # greater element on the left side vec = [-1 for i in range(n)] # Stack to store the pairs st = [] i = n - 1 while(i >= 0): # If the stack is empty, push the pair if (len(st) == 0): st.append(B[i]) else: # Pop and assign till top is smaller while (len(st) > 0 and st[-1][0] < B[i][0]): vec[st[-1][1]] = B[i][1] st.pop() st.append(B[i]) i -= 1 # Assign -1 to element having # no next greater element while (len(st) > 0): vec[st[-1][1]] = -1 st.pop() # Returning the vector # with indices of next greater # elements on the left side. return vec # Function to print the maximum # length of subarrays for all # indices where A[i] is the # maximum element in the subarray def maximumSubarrayLength(arr, N): # Array having index of next # greater element on the right side. right = rightGreaterElement(arr, N) # Array having index of next # greater element on the left side. left = leftGreaterElement(arr, N) # Print the range between the # next greater elements on both the sides. for i in range(N): l = left[i] r = right[i] print(r - l - 1, end = " ") # Driver code if __name__ == '__main__': # Input arr = [ 62, 97, 49, 59, 54, 92, 21 ] N = len(arr) # Function call maximumSubarrayLength(arr, N) # This code is contributed by ipg2016107
C#
// C# code for the above approach
using System;
using System.Collections;
class GFG {
// Function to compute
// next greater element indices on the
// right side on any index
static int[] rightGreaterElement(int[] arr, int n)
{
// to store the elements of array arr
// with their index
int[,] B = new int[n,2];
for (int i = 0; i < n; i++) {
B[i,0] = arr[i];
B[i,1] = i;
}
// to store indices of next greater element
// on the right side
int[] vec = new int[n];
Array.Fill(vec, -1);
// to store the pairs
Stack st = new Stack();
for (int i = 0; i < n; i++) {
// if the stack is empty,
// push the pair
if (st.Count == 0) {
st.Push(new Tuple<int,int>(B[i,0], B[i,1]));
}
else {
// Pop and assign till
// the top is smaller
while (st.Count > 0
&& ((Tuple<int,int>)st.Peek()).Item1 < B[i,0]) {
vec[((Tuple<int,int>)st.Peek()).Item2] = B[i,1];
st.Pop();
}
st.Push(new Tuple<int,int>(B[i,0], B[i,1]));
}
}
// assign n to element
// having no next greater element
while (st.Count > 0) {
vec[((Tuple<int,int>)st.Peek()).Item2] = n;
st.Pop();
}
// return the vector
return vec;
}
// Function to compute next greater element
// indices on the left side on any index
static int[] leftGreaterElement(int[] arr, int n)
{
// store the elements of array arr
// with their index
int[,] B = new int[n,2];
for (int i = 0; i < n; i++) {
B[i,0] = arr[i];
B[i,1] = i;
}
// array to store indices of next
// greater element on the left side
int[] vec = new int[n];
Array.Fill(vec, -1);
// stack to store the pairs
Stack st = new Stack();
for (int i = n - 1; i >= 0; i--) {
// if the stack is empty, push the pair
if (st.Count == 0) {
st.Push(new Tuple<int,int>(B[i,0], B[i,1]));
}
else {
// pop and assign till top is smaller
while (st.Count > 0
&& ((Tuple<int,int>)st.Peek()).Item1 < B[i,0]) {
vec[((Tuple<int,int>)st.Peek()).Item2] = B[i,1];
st.Pop();
}
st.Push(new Tuple<int,int>(B[i,0], B[i,1]));
}
}
// assign -1 to element having
// no next greater element
while (st.Count > 0) {
vec[((Tuple<int,int>)st.Peek()).Item2] = -1;
st.Pop();
}
// returning the vector
// with indices of next greater
// elements on the left side.
return vec;
}
// Function to print the maximum
// length of subarrays for all
// indices where A[i] is the
// maximum element in the subarray
static void maximumSubarrayLength(int[] arr, int N)
{
// array having index of next
// greater element on the right side.
int[] right = rightGreaterElement(arr, N);
// array having index of next
// greater element on the left side.
int[] left = leftGreaterElement(arr, N);
// print the range between the
// next greater elements on both the sides.
for (int i = 0; i < N; i++) {
int l = left[i];
int r = right[i];
Console.Write((r - l - 1) + " ");
}
}
static void Main()
{
// Input
int[] arr = { 62, 97, 49, 59, 54, 92, 21 };
int N = arr.Length;
// Function call
maximumSubarrayLength(arr, N);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript code for the above approach
// Function to compute
// next greater element indices on the
// right side on any index
function rightGreaterElement(arr, n) {
// to store the elements of array arr
// with their index
let B = new Array(n).fill(0).map(() => new Array(2).fill(0));
for (let i = 0; i < n; i++) {
B[i][0] = arr[i];
B[i][1] = i;
}
// to store indices of next greater element
// on the right side
let vec = new Array(n).fill(-1);
// to store the pairs
let st = [];
for (let i = 0; i < n; i++) {
// if the stack is empty,
// push the pair
if (st.length == 0) {
st.push(B[i]);
}
else {
// Pop and assign till
// the top is smaller
while (st.length > 0
&& st[st.length - 1][0] < B[i][0]) {
vec[st[st.length - 1][1]] = B[i][1];
st.pop();
}
st.push(B[i]);
}
}
// assign n to element
// having no next greater element
while (st.length > 0) {
vec[st[st.length - 1][1]] = n;
st.pop();
}
// return the vector
return vec;
}
// Function to compute next greater element
// indices on the left side on any index
function leftGreaterElement(arr, n) {
// store the elements of array arr
// with their index
let B = new Array(n).fill(0).map(() => new Array(2));
for (let i = 0; i < n; i++) {
B[i][0] = arr[i];
B[i][1] = i;
}
// array to store indices of next
// greater element on the left side
let vec = new Array(n).fill(-1);
// stack to store the pairs
let st = [];
for (let i = n - 1; i >= 0; i--) {
// if the stack is empty, push the pair
if (st.length == 0) {
st.push(B[i]);
}
else {
// pop and assign till top is smaller
while (st.length > 0
&& st[st.length - 1][0] < B[i][0]) {
vec[st[st.length - 1][1]] = B[i][1];
st.pop();
}
st.push(B[i]);
}
}
// assign -1 to element having
// no next greater element
while (st.length > 0) {
vec[st[st.length - 1][1]] = -1;
st.pop();
}
// returning the vector
// with indices of next greater
// elements on the left side.
return vec;
}
// Function to print the maximum
// length of subarrays for all
// indices where A[i] is the
// maximum element in the subarray
function maximumSubarrayLength(arr, N)
{
// array having index of next
// greater element on the right side.
let right = rightGreaterElement(arr, N);
// array having index of next
// greater element on the left side.
let left = leftGreaterElement(arr, N);
// print the range between the
// next greater elements on both the sides.
for (let i = 0; i < N; i++) {
let l = left[i];
let r = right[i];
document.write(r - l - 1 + " ");
}
}
// Driver code
// Input
let arr = [62, 97, 49, 59, 54, 92, 21];
let N = arr.length;
// Function call
maximumSubarrayLength(arr, N);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción
1 7 1 3 1 5 1
Tiempo Complejidad: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sudhanshugupta2019a y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA