Recuento de subarreglos que comienzan o terminan en un índice i tal que arr[i] es el máximo en el subarreglo

Dado un arreglo arr[] que consta de N enteros, la tarea es encontrar el número de subarreglos que comienzan o terminan en un índice i tal que arr[i] es el elemento máximo del subarreglo.

Ejemplos:

Entrada: arr[] = {3, 4, 1, 6, 2}
Salida: 1 3 1 5 1
Explicación:

1. El subarreglo que comienza o termina en el índice 0 y con el máximo arr[0](=3) es {3}. Por lo tanto, la cuenta es 1.
2. Los subarreglos que comienzan o terminan en el índice 1 y con un arreglo máximo[1](=4) son {3, 4}, {4} y {4, 1}. Por lo tanto, la cuenta es 3.
3. El subarreglo que comienza o termina en el índice 2 y con el máximo arr[2](=1) es {1}. Por lo tanto, la cuenta es 1.
4. Los subarreglos que comienzan o terminan en el índice 3 y con un arreglo máximo[3](=6) son {3, 4, 1, 6}, {4, 1, 6}, {1, 6}, {6} y { 6, 2}. Por lo tanto, la cuenta es 5.
5. El subarreglo que comienza o termina en el índice 4 y con el máximo arr[4](=2) es {2}. Por lo tanto, la cuenta es 1.

Entrada: arr[] = {1, 2, 3}
Salida: 1 2 3

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es para cada i ^-ésimo índice, iterar hacia atrás y hacia adelante hasta que el máximo del subarreglo permanezca igual a arr[i] y luego imprimir el recuento total de subarreglos obtenidos.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar almacenando el índice del siguiente elemento mayor y el elemento mayor anterior para cada índice i y encontrar el recuento de subarreglos en consecuencia para cada índice. Siga los pasos a continuación para resolver el problema dado:

• Inicialice dos arreglos , digamos pge[] y nge[], para almacenar el índice del elemento mayor anterior y el siguiente elemento mayor para cada índice i .
• Encuentre el índice del elemento mayor anterior para cada índice y almacene la array resultante en pge[] .
• Encuentre el índice del siguiente elemento mayor para cada índice y almacene la array resultante en nge[] .
• Iterar sobre el rango [0, N – 1] y usando la variable i y en cada iteración imprimir, el conteo de subarreglos comenzando o terminando en el índice i y con arr[i] como máximo como nge[i] + pge[i ] – 1 e imprime este conteo.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find previous greater
// element
int* getPGE(int arr[], int n)
{
     
    // Stores the previous greater
    // element for each index
    int* pge = new int[n];
    stack<int> stack;
 
    // Traverse the array
    for(int i = 0; i < n; i++)
    {
         
        // Iterate until stack is empty
        // and top element is less than
        // the current element arr[i]
        while (!stack.empty() &&
            arr[stack.top()] <= arr[i])
        {
            stack.pop();
        }
 
        // Update the previous greater
        // element for arr[i]
        pge[i] = stack.empty() ? -1 : stack.top();
 
        // Push the current index to
        // the stack
        stack.push(i);
    }
 
    // Return the PGE[] array
    return pge;
}
 
// Function to find the Next Greater Element
int* getNGE(int arr[], int n)
{
     
    // Stores the next greater element
    // for each index
    int* nge = new int[n];
    stack<int> stack;
 
    // Traverse the array from the back
    for(int i = n - 1; i >= 0; i--)
    {
         
        // Iterate until stack is empty
        // and top element is less than
        // the current element arr[i]
        while (!stack.empty() &&
            arr[stack.top()] <= arr[i])
        {
            stack.pop();
        }
 
        // Update the next greater
        // element for arr[i]
        nge[i] = stack.empty() ? n : stack.top();
 
        // Push the current index
        stack.push(i);
    }
 
    // Return the NGE[] array
    return nge;
}
 
// Function to find the count of
// subarrays starting or ending at
// index i having arr[i] as maximum
void countSubarrays(int arr[], int n)
{
     
    // Function call to find the
    // previous greater element
    // for each array elements
    int* pge = getPGE(arr, n);
 
    // Function call to find the
    // previous greater element
    // for each elements
    int* nge = getNGE(arr, n);
 
    // Traverse the array arr[]
    for(int i = 0; i < n; i++)
    {
         
        // Print count of subarrays
        // satisfying the conditions
        cout << nge[i] - pge[i] - 1 << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 4, 1, 6, 2 };
     
    int n = sizeof(arr) / sizeof(arr[0]);
     
    countSubarrays(arr, n);
     
    return 0;
}
 
// This code is contributed by Potta Lokesh

// Java program for the above approach
import java.util.*;
 
public class GFG {
 
    // Function to find previous greater
    // element
    private static int[] getPGE(int[] arr)
    {
        // Stores the previous greater
        // element for each index
        int[] pge = new int[arr.length];
        Stack<Integer> stack = new Stack<>();
 
        // Traverse the array
        for (int i = 0; i < arr.length; i++) {
 
            // Iterate until stack is empty
            // and top element is less than
            // the current element arr[i]
            while (!stack.isEmpty()
                   && arr[stack.peek()] <= arr[i]) {
                stack.pop();
            }
 
            // Update the previous greater
            // element for arr[i]
            pge[i] = stack.isEmpty() ? -1 : stack.peek();
 
            // Push the current index to
            // the stacl
            stack.push(i);
        }
 
        // Return the PGE[] array
        return pge;
    }
 
    // Function to find the Next Greater Element
    private static int[] getNGE(int[] arr)
    {
        // Stores the next greater element
        // for each index
        int[] nge = new int[arr.length];
        Stack<Integer> stack = new Stack<>();
 
        // Traverse the array from the back
        for (int i = arr.length - 1; i >= 0; i--) {
 
            // Iterate until stack is empty
            // and top element is less than
            // the current element arr[i]
            while (!stack.isEmpty()
                   && arr[stack.peek()] <= arr[i]) {
                stack.pop();
            }
 
            // Update the next greater
            // element for arr[i]
            nge[i] = stack.isEmpty() ? arr.length
                                     : stack.peek();
 
            // Push the current index
            stack.push(i);
        }
 
        // Return the NGE[] array
        return nge;
    }
 
    // Function to find the count of
    // subarrays starting or ending at
    // index i having arr[i] as maximum
    private static void countSubarrays(int[] arr)
    {
 
        // Function call to find the
        // previous greater element
        // for each array elements
        int[] pge = getPGE(arr);
 
        // Function call to find the
        // previous greater element
        // for each elements
        int[] nge = getNGE(arr);
 
        // Traverse the array arr[]
        for (int i = 0; i < arr.length; i++) {
 
            // Print count of subarrays
            // satisfying the conditions
            System.out.print(
                nge[i] - pge[i] - 1 + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = new int[] { 3, 4, 1, 6, 2 };
        countSubarrays(arr);
    }
}

# Python program for the above approach
# Stores the previous greater
# element for each index
pge = []
 
# Stores the next greater element
# for each index
nge = []
 
# Function to find previous greater
# element
def getPGE(arr, n) :
  s = list()
   
  # Traverse the array
  for i in range(0, n):
     
    # Iterate until stack is empty
    # and top element is less than
    # the current element arr[i]
    while (len(s) > 0 and arr[s[-1]] <= arr[i]):
      s.pop()
       
    # Update the previous greater
    # element for arr[i]
    if len(s) == 0:
      pge.append(-1)
    else:
      pge.append(s[-1])
       
    # Push the current index
    s.append(i)
     
# Function to find the Next Greater Element  
def getNGE(arr, n) :
  s = list()
   
  # Traverse the array from the back
  for i in range(n-1, -1, -1):
     
    # Iterate until stack is empty
    # and top element is less than
    # the current element arr[i]
    while (len(s) > 0 and arr[s[-1]] <= arr[i]):
      s.pop()
       
    # Update the next greater
    # element for arr[i]
    if len(s) == 0:
      nge.append(n)
    else:
      nge.append(s[-1])
       
    # Push the current index
    s.append(i)
  nge.reverse();
   
# Function to find the count of
# subarrays starting or ending at
# index i having arr[i] as maximum
def countSubarrays(arr, n):
   
  # Function call to find the
  # previous greater element
  # for each array elements
  getNGE(arr, n);
   
  # Function call to find the
  # previous greater element
  # for each elements
  getPGE(arr, n);
   
  # Traverse the array arr[]
  for i in range(0,n):
    print(nge[i]-pge[i]-1,end = " ")
 
arr = [ 3, 4, 1, 6, 2 ]
n = len(arr)
countSubarrays(arr,n);
 
# This code is contributed by codersaty

// C# program for the above approach
using System;
using System.Collections;
class GFG {
     
    // Function to find previous greater
    // element
    static int[] getPGE(int[] arr)
    {
       
        // Stores the previous greater
        // element for each index
        int[] pge = new int[arr.Length];
        Stack stack = new Stack();
  
        // Traverse the array
        for (int i = 0; i < arr.Length; i++) {
  
            // Iterate until stack is empty
            // and top element is less than
            // the current element arr[i]
            while (stack.Count > 0 && arr[(int)stack.Peek()] <= arr[i]) {
                stack.Pop();
            }
  
            // Update the previous greater
            // element for arr[i]
            pge[i] = stack.Count == 0 ? -1 : (int)stack.Peek();
  
            // Push the current index to
            // the stacl
            stack.Push(i);
        }
  
        // Return the PGE[] array
        return pge;
    }
  
    // Function to find the Next Greater Element
    static int[] getNGE(int[] arr)
    {
        // Stores the next greater element
        // for each index
        int[] nge = new int[arr.Length];
        Stack stack = new Stack();
  
        // Traverse the array from the back
        for (int i = arr.Length - 1; i >= 0; i--) {
  
            // Iterate until stack is empty
            // and top element is less than
            // the current element arr[i]
            while (stack.Count > 0 && arr[(int)stack.Peek()] <= arr[i]) {
                stack.Pop();
            }
  
            // Update the next greater
            // element for arr[i]
            nge[i] = stack.Count == 0 ? arr.Length : (int)stack.Peek();
  
            // Push the current index
            stack.Push(i);
        }
  
        // Return the NGE[] array
        return nge;
    }
  
    // Function to find the count of
    // subarrays starting or ending at
    // index i having arr[i] as maximum
    static void countSubarrays(int[] arr)
    {
  
        // Function call to find the
        // previous greater element
        // for each array elements
        int[] pge = getPGE(arr);
  
        // Function call to find the
        // previous greater element
        // for each elements
        int[] nge = getNGE(arr);
  
        // Traverse the array arr[]
        for (int i = 0; i < arr.Length; i++) {
  
            // Print count of subarrays
            // satisfying the conditions
            Console.Write((nge[i] - pge[i] - 1) + " ");
        }
    }
     
  // Driver code
  static void Main() {
    int[] arr = { 3, 4, 1, 6, 2 };
    countSubarrays(arr);
  }
}
 
// This code is contributed by divyesh072019.

<script>
// Javascript program for the above approach
// Stores the previous greater
// element for each index
let pge = [];
 
// Stores the next greater element
// for each index
let nge = [];
 
// Function to find previous greater
// element
function getPGE(arr, n) {
  let s = [];
 
  // Traverse the array
  for (let i = 0; i < n; i++)
  {
   
    // Iterate until stack is empty
    // and top element is less than
    // the current element arr[i]
    while (s.length > 0 && arr[s[s.length - 1]] <= arr[i])
    {
      s.pop();
    }
 
    // Update the previous greater
    // element for arr[i]
    if (s.length == 0) pge.push(-1);
    else pge.push(s[s.length - 1]);
 
    // Push the current index
    s.push(i);
  }
}
 
// Function to find the Next Greater Element
function getNGE(arr, n) {
  let s = [];
 
  // Traverse the array from the back
  for (let i = n - 1; i >= 0; i--)
  {
   
    // Iterate until stack is empty
    // and top element is less than
    // the current element arr[i]
    while (s.length > 0 && arr[s[s.length - 1]] <= arr[i]) {
      s.pop();
    }
 
    // Update the next greater
    // element for arr[i]
    if (s.length == 0) nge.push(n);
    else nge.push(s[s.length - 1]);
 
    // Push the current index
    s.push(i);
  }
  nge.reverse();
}
 
// Function to find the count of
// subarrays starting or ending at
// index i having arr[i] as maximum
function countSubarrays(arr, n)
{
 
  // Function call to find the
  // previous greater element
  // for each array elements
  getNGE(arr, n);
 
  // Function call to find the
  // previous greater element
  // for each elements
  getPGE(arr, n);
 
  // Traverse the array arr[]
  for (let i = 0; i < n; i++) {
    document.write(nge[i] - pge[i] - 1 + " ");
  }
}
 
let arr = [3, 4, 1, 6, 2];
let n = arr.length;
countSubarrays(arr, n);
 
// This code is contributed by _saurabh_jaiswal
 
</script>

1 3 1 5 1

Complejidad temporal: O(N)
Espacio auxiliar: O(N)