Longitud de rango máxima tal que A[i] es máxima en el rango dado para todos los i de [1, N]

Dada una array arr[] que consta de N enteros distintos. Para cada i (0 ≤ i < n), encuentre un rango [l, r] tal que A[i] = max(A[l], A[l+1], …, A[r]) y l ≤ i ≤ r y rl se maximiza.

Ejemplos:

Entrada: arr[] = {1, 3, 2}
Salida: {0 0}, {0 2}, {2 2}
Explicación: Para i=0, 1 es el máximo en el rango [0, 0] solamente. Para i=1, 3 es el máximo en el rango [0, 2] y para i = 2, 2 es el máximo en el rango [2, 2] solamente.

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

Enfoque ingenuo: el enfoque más simple para resolver el problema es para cada i , iterar en el rango [i+1, N-1] usando la variable r e iterar en el rango [i-1, 0] usando la variable l y terminar el bucle cuando arr[l] > arr[i] y arr[r]>arr[i] respectivamente. La respuesta será [l, r] . 

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

Enfoque eficiente: el enfoque anterior se puede optimizar aún más mediante el uso de una estructura de datos de pila . Siga los pasos a continuación para resolver el problema:

• Inicialice dos vectores , digamos izquierdo y derecho , que almacenarán el índice izquierdo y el índice derecho para cada i respectivamente.
• Inicialice una pila de pares , digamos s .
• Inserte INT_MAX y -1 como un par en la pila.
• Iterar en el rango [0, N-1] usando la variable i y realizar los siguientes pasos:
  • Mientras s.top().first<arr[i] , saca el elemento superior de la pila.
  • Modifique el valor de left[i] como s.top().second .
  • Empuje {arr[i], i} en la pila .
• Ahora elimine todos los elementos de la pila.
• Inserte INT_MAX y N en la pila como pares.
• Iterar en el rango [N-1, 0] usando la variable i y realizar los siguientes pasos:
  • Mientras s.top().first<arr[i] , saca el elemento superior de la pila.
  • Modifique el valor de right[i] como s.top().second .
  • Empuje {arr[i], i} en la pila .
• Iterar en el rango [0, N-1] usando la variable i e imprimir left[i] +1 , right[i] -1 como la respuesta para el i-ésimo elemento.

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 maximum range for
// each i such that arr[i] is max in range
void MaxRange(vector<int> A, int n)
{
    // Vector to store the left and right index
    // for each i such that left[i]>arr[i]
    // and right[i] > arr[i]
    vector<int> left(n), right(n);
 
    stack<pair<int, int> > s;
    s.push({ INT_MAX, -1 });
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
        // While s.top().first<a[i]
        // remove the top element from
        // the stack
        while (s.top().first < A[i])
            s.pop();
 
        // Modify left[i]
        left[i] = s.top().second;
        s.push({ A[i], i });
    }
    // Clear the stack
    while (!s.empty())
        s.pop();
    s.push(make_pair(INT_MAX, n));
 
    // Traverse the array to find
    // right[i] for each i
    for (int i = n - 1; i >= 0; i--) {
        // While s.top().first<a[i]
        // remove the top element from
        // the stack
        while (s.top().first < A[i])
            s.pop();
 
        // Modify right[i]
        right[i] = s.top().second;
        s.push({ A[i], i });
    }
 
    // Print the value range for each i
    for (int i = 0; i < n; i++) {
        cout << left[i] + 1 << ' ' << right[i] - 1 << "\n";
    }
}
 
// Driver Code
int main()
{
    // Given Input
    vector<int> arr{ 1, 3, 2 };
    int n = arr.size();
 
    // Function Call
    MaxRange(arr, n);
 
    return 0;
}

//Java program for above approach
import java.awt.*;
import java.util.*;
class GFG{
    static class pair<T, V>{
        T first;
        V second;
    }
 
    // Function to find maximum range for
    // each i such that arr[i] is max in range
    static void MaxRange(ArrayList<Integer> A, int n)
    {
        // Vector to store the left and right index
        // for each i such that left[i]>arr[i]
        // and right[i] > arr[i]
 
        int[] left = new int[n];
        int[] right = new int[n];
 
        Stack<pair<Integer,Integer>> s = new Stack<>();
        pair<Integer,Integer> x = new pair<>();
        x.first =Integer.MAX_VALUE;
        x.second = -1;
        s.push(x);
 
        // Traverse the array
        for (int i = 0; i < n; i++)
        {
           
            // While s.top().first<a[i]
            // remove the top element from
            // the stack
            while (s.peek().first < A.get(i))
                s.pop();
 
            // Modify left[i]
            left[i] = s.peek().second;
            pair<Integer,Integer> y = new pair<>();
            y.first = A.get(i);
            y.second = i;
            s.push(y);
        }
       
        // Clear the stack
        while (!s.empty())
            s.pop();
        pair<Integer,Integer> k = new pair<>();
        k.first =Integer.MAX_VALUE;
        k.second = n;
        s.push(k);
 
        // Traverse the array to find
        // right[i] for each i
        for (int i = n - 1; i >= 0; i--)
        {
           
            // While s.top().first<a[i]
            // remove the top element from
            // the stack
            while (s.peek().first < A.get(i))
                s.pop();
 
            // Modify right[i]
            right[i] = s.peek().second;
            pair<Integer,Integer> y = new pair<>();
            y.first = A.get(i);
            y.second = i;
            s.push(y);
        }
       
        // Print the value range for each i
        for (int i = 0; i < n; i++) {
            System.out.print(left[i]+1);
            System.out.print(" ");
            System.out.println(right[i]-1);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
       
        // Given Input
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(1);
        arr.add(3);
        arr.add(2);
        int n = arr.size();
 
        // Function Call
        MaxRange(arr, n);
    }
}
 
// This code is contributed by hritikrommie.

# Python 3 program for the above approach
import sys
 
# Function to find maximum range for
# each i such that arr[i] is max in range
def MaxRange(A, n):
 
    # Vector to store the left and right index
    # for each i such that left[i]>arr[i]
    # and right[i] > arr[i]
    left = [0] * n
    right = [0] * n
 
    s = []
    s.append((sys.maxsize, -1))
 
    # Traverse the array
    for i in range(n):
       
        # While s.top().first<a[i]
        # remove the top element from
        # the stack
        while (s[-1][0] < A[i]):
            s.pop()
 
        # Modify left[i]
        left[i] = s[-1][1]
        s.append((A[i], i))
 
    # Clear the stack
    while (len(s) != 0):
        s.pop()
    s.append((sys.maxsize, n))
 
    # Traverse the array to find
    # right[i] for each i
    for i in range(n - 1, -1, -1):
       
        # While s.top().first<a[i]
        # remove the top element from
        # the stack
        while (s[-1][0] < A[i]):
            s.pop()
 
        # Modify right[i]
        right[i] = s[-1][1]
        s.append((A[i], i))
 
    # Print the value range for each i
    for i in range(n):
        print(left[i] + 1, ' ', right[i] - 1)
 
 
# Driver Code
if __name__ == "__main__":
   
    # Given Input
    arr = [1, 3, 2]
    n = len(arr)
 
    # Function Call
    MaxRange(arr, n)
 
    # This code is contributed by ukasp.

// C# program for the above approach.
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
     
    // Function to find maximum range for
    // each i such that arr[i] is max in range
    static void MaxRange(List<int> A, int n)
    {
        // Vector to store the left and right index
        // for each i such that left[i]>arr[i]
        // and right[i] > arr[i]
        int[] left = new int[n];
        int[] right = new int[n];
      
        Stack s = new Stack();
        s.Push(new Tuple<int, int>(Int32.MaxValue, -1));
      
        // Traverse the array
        for (int i = 0; i < n; i++)
        {
           
            // While s.top().first<a[i]
            // remove the top element from
            // the stack
            while (((Tuple<int, int>)s.Peek()).Item1 < A[i])
                s.Pop();
      
            // Modify left[i]
            left[i] = ((Tuple<int, int>)s.Peek()).Item2;
            s.Push(new Tuple<int, int>(A[i], i));
        }
        // Clear the stack
        while (s.Count > 0)
            s.Pop();
        s.Push(new Tuple<int, int>(Int32.MaxValue, n));
      
        // Traverse the array to find
        // right[i] for each i
        for (int i = n - 1; i >= 0; i--) {
            // While s.top().first<a[i]
            // remove the top element from
            // the stack
            while (((Tuple<int, int>)s.Peek()).Item1 < A[i])
                s.Pop();
      
            // Modify right[i]
            right[i] = ((Tuple<int, int>)s.Peek()).Item2;
            s.Push(new Tuple<int, int>(A[i], i));
        }
      
        // Print the value range for each i
        for (int i = 0; i < n; i++) {
            Console.WriteLine((left[i] + 1) + " " + (right[i] - 1));
        }
    }
     
  static void Main ()
  {
    List<int> arr = new List<int>();
   
    // adding elements in firstlist
    arr.Add(1);
    arr.Add(3);
    arr.Add(2);
     
    int n = arr.Count;
  
    // Function Call
    MaxRange(arr, n);
  }
}
 
// This code is contributed by suresh07.

<script>
 
// Javascript program for the above approach
 
// Function to find maximum range for
// each i such that arr[i] is max in range
function MaxRange(A, n)
{
     
    // Vector to store the left and right index
    // for each i such that left[i]>arr[i]
    // and right[i] > arr[i]
    let left = new Array(n).fill(0),
       right = new Array(n).fill(0);
 
    let s = [];
    s.push([Number.MAX_SAFE_INTEGER, -1]);
 
    // Traverse the array
    for(let i = 0; i < n; i++)
    {
         
        // While s.top()[0]<a[i]
        // remove the top element from
        // the stack
        while (s[s.length - 1][0] < A[i])
            s.pop();
 
        // Modify left[i]
        left[i] = s[s.length - 1][1];
        s.push([A[i], i]);
    }
     
    // Clear the stack
    while (s.length)
        s.pop();
         
    s.push([Number.MAX_SAFE_INTEGER, n]);
 
    // Traverse the array to find
    // right[i] for each i
    for(let i = n - 1; i >= 0; i--)
    {
         
        // While s.top()[0]<a[i]
        // remove the top element from
        // the stack
        while (s[s.length - 1][0] < A[i])
            s.pop();
 
        // Modify right[i]
        right[i] = s[s.length - 1][1];
        s.push([A[i], i]);
    }
 
    // Print the value range for each i
    for(let i = 0; i < n; i++)
    {
        document.write(left[i] + 1 + " ")
        document.write(right[i] - 1 + "<br>")
    }
}
 
// Driver Code
 
// Given Input
let arr = [ 1, 3, 2 ];
let n = arr.length;
 
// Function Call
MaxRange(arr, n);
 
// This code is contributed by gfgking
 
</script>

0 0
0 2
2 2

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