Dada una array de N elementos distintos de al menos tamaño 2. Un par (a, b) en una array se define como ‘a’ es el índice del segundo elemento más alto y ‘b’ es el índice del elemento más alto en la array. La tarea es contar todos los pares distintos donde a < b en todos los subarreglos.
Ejemplos:
Input : arr[] = { 1, 3, 2, 4 }
Output : 3
Explicación :
The subarray { 1 }, { 3 }, { 2 }, { 4 } does not contain any such pair
The subarray { 1, 3 }, { 2, 4 } contain (1, 2) as pair
The subarray { 3, 2 } does not contain any such pair
The subarray { 3, 2, 4 } contain (1, 3) as a pair
The subarray { 1, 3, 2 } does not contain any such pair
The subarray { 1, 3, 2, 4 } contain (2, 4) as a pair
So, there are 3 distinct pairs, which are (1, 2), (1, 3) and (2, 4).
Método 1: (Fuerza bruta): El enfoque simple puede ser,
- Encuentre todos los subarreglos.
- Para cada subarreglo, encuentre el segundo elemento más grande y más grande.
- Compruebe si el segundo elemento más grande se encuentra antes del elemento más grande.
- Si es así, compruebe si dicho par de índices ya está contado o no. Si no, almacene el par e incremente el conteo en 1, de lo contrario, ignórelo.
Complejidad Temporal: O(n 2 ).
Método 2: (usando la pila):
Para una array A dada, suponga que para un elemento en el índice curr (A[curr]), el primer elemento mayor que él y después de él es A[next] y el primer elemento mayor que él y antes de él A[prev]. Observe que para todos los subarreglos que comienzan desde cualquier índice en el rango [prev + 1, curr] y terminan en el índice next, A[curr] es el segundo más grande y A[next] es el más grande, lo que genera (curr – prev + 1) pares en total con diferencia de (siguiente – curr + 1) en máximo y segundo máximo.
Si obtenemos el elemento mayor siguiente y anterior en una array, y hacemos un seguimiento del número máximo de pares posibles para cualquier diferencia (del mayor y el segundo más grande). Tendremos que sumar todos estos números.
Ahora el único trabajo que queda es obtener un elemento mayor (después y antes) de cualquier elemento. Para ello, consulte Elemento mayor siguiente .
Recorra desde el elemento inicial en una array, realizando un seguimiento de todos los números en la pila en orden decreciente. Después de llegar a cualquier número, extraiga todos los elementos de la pila que son menores que el elemento actual para obtener la ubicación del número mayor que él y empuje el elemento actual en él. Esto genera el valor requerido para todos los números en la array.
Implementación:
C++
// C++ program to count number of distinct instance
// where second highest number lie
// before highest number in all subarrays.
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
// Finding the next greater element of the array.
void makeNext(int arr[], int n, int nextBig[])
{
stack<pair<int, int> > s;
for (int i = n - 1; i >= 0; i--) {
nextBig[i] = i;
while (!s.empty() && s.top().first < arr[i])
s.pop();
if (!s.empty())
nextBig[i] = s.top().second;
s.push(pair<int, int>(arr[i], i));
}
}
// Finding the previous greater element of the array.
void makePrev(int arr[], int n, int prevBig[])
{
stack<pair<int, int> > s;
for (int i = 0; i < n; i++) {
prevBig[i] = -1;
while (!s.empty() && s.top().first < arr[i])
s.pop();
if (!s.empty())
prevBig[i] = s.top().second;
s.push(pair<int, int>(arr[i], i));
}
}
// Wrapper Function
int wrapper(int arr[], int n)
{
int nextBig[MAXN];
int prevBig[MAXN];
int maxi[MAXN];
int ans = 0;
// Finding previous largest element
makePrev(arr, n, prevBig);
// Finding next largest element
makeNext(arr, n, nextBig);
for (int i = 0; i < n; i++)
if (nextBig[i] != i)
maxi[nextBig[i] - i] = max(maxi[nextBig[i] - i],
i - prevBig[i]);
for (int i = 0; i < n; i++)
ans += maxi[i];
return ans;
}
// Driven Program
int main()
{
int arr[] = { 1, 3, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << wrapper(arr, n) << endl;
return 0;
}
Java
// Java program to count number of distinct instance
// where second highest number lie
// before highest number in all subarrays.
import java.util.*;
class GFG
{
static int MAXN = 100005;
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Finding the next greater element of the array.
static void makeNext(int arr[], int n, int nextBig[])
{
Stack<pair> s = new Stack<>();
for (int i = n - 1; i >= 0; i--)
{
nextBig[i] = i;
while (!s.empty() && s.peek().first < arr[i])
s.pop();
if (!s.empty())
nextBig[i] = s.peek().second;
s.push(new pair(arr[i], i));
}
}
// Finding the previous greater element of the array.
static void makePrev(int arr[], int n, int prevBig[])
{
Stack<pair> s = new Stack<>();
for (int i = 0; i < n; i++)
{
prevBig[i] = -1;
while (!s.empty() && s.peek().first < arr[i])
s.pop();
if (!s.empty())
prevBig[i] = s.peek().second;
s.push(new pair(arr[i], i));
}
}
// Wrapper Function
static int wrapper(int arr[], int n)
{
int []nextBig = new int[MAXN];
int []prevBig = new int[MAXN];
int []maxi = new int[MAXN];
int ans = 0;
// Finding previous largest element
makePrev(arr, n, prevBig);
// Finding next largest element
makeNext(arr, n, nextBig);
for (int i = 0; i < n; i++)
if (nextBig[i] != i)
maxi[nextBig[i] - i] = Math.max(maxi[nextBig[i] - i],
i - prevBig[i]);
for (int i = 0; i < n; i++)
ans += maxi[i];
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 3, 2, 4 };
int n = arr.length;
System.out.println(wrapper(arr, n));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to count number of distinct # instance where second highest number lie # before highest number in all subarrays. from typing import List MAXN = 100005 # Finding the next greater element # of the array. def makeNext(arr: List[int], n: int, nextBig: List[int]) -> None: # Stack s = [] for i in range(n - 1, -1, -1): nextBig[i] = i while len(s) and s[-1][0] < arr[i]: s.pop() if len(s): nextBig[i] = s[-1][1] s.append((arr[i], i)) # Finding the previous greater # element of the array. def makePrev(arr: List[int], n: int, prevBig: List[int]) -> None: # Stack s = [] for i in range(n): prevBig[i] = -1 while (len(s) and s[-1][0] < arr[i]): s.pop() if (len(s)): prevBig[i] = s[-1][1] s.append((arr[i], i)) # Wrapper Function def wrapper(arr: List[int], n: int) -> int: nextBig = [0] * MAXN prevBig = [0] * MAXN maxi = [0] * MAXN ans = 0 # Finding previous largest element makePrev(arr, n, prevBig) # Finding next largest element makeNext(arr, n, nextBig) for i in range(n): if (nextBig[i] != i): maxi[nextBig[i] - i] = max( maxi[nextBig[i] - i], i - prevBig[i]) for i in range(n): ans += maxi[i] return ans # Driver Code if __name__ == "__main__": arr = [ 1, 3, 2, 4 ] n = len(arr) print(wrapper(arr, n)) # This code is contributed by sanjeev2552
C#
// C# program to count number of distinct instance
// where second highest number lie
// before highest number in all subarrays.
using System;
using System.Collections.Generic;
class GFG
{
static int MAXN = 100005;
public class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Finding the next greater element of the array.
static void makeNext(int []arr, int n, int []nextBig)
{
Stack<pair> s = new Stack<pair>();
for (int i = n - 1; i >= 0; i--)
{
nextBig[i] = i;
while (s.Count!=0 && s.Peek().first < arr[i])
s.Pop();
if (s.Count!=0)
nextBig[i] = s.Peek().second;
s.Push(new pair(arr[i], i));
}
}
// Finding the previous greater element of the array.
static void makePrev(int []arr, int n, int[] prevBig)
{
Stack<pair> s = new Stack<pair>();
for (int i = 0; i < n; i++)
{
prevBig[i] = -1;
while (s.Count!=0 && s.Peek().first < arr[i])
s.Pop();
if (s.Count!=0)
prevBig[i] = s.Peek().second;
s.Push(new pair(arr[i], i));
}
}
// Wrapper Function
static int wrapper(int []arr, int n)
{
int []nextBig = new int[MAXN];
int []prevBig = new int[MAXN];
int []maxi = new int[MAXN];
int ans = 0;
// Finding previous largest element
makePrev(arr, n, prevBig);
// Finding next largest element
makeNext(arr, n, nextBig);
for (int i = 0; i < n; i++)
if (nextBig[i] != i)
maxi[nextBig[i] - i] = Math.Max(maxi[nextBig[i] - i],
i - prevBig[i]);
for (int i = 0; i < n; i++)
ans += maxi[i];
return ans;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 1, 3, 2, 4 };
int n = arr.Length;
Console.WriteLine(wrapper(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to count number of distinct instance
// where second highest number lie
// before highest number in all subarrays.
var MAXN = 100005;
// Finding the next greater element of the array.
function makeNext(arr, n, nextBig)
{
var s = [];
for (var i = n - 1; i >= 0; i--) {
nextBig[i] = i;
while (s.length!=0 && s[s.length-1][0] < arr[i])
s.pop();
if (s.length!=0)
nextBig[i] = s[s.length-1][1];
s.push([arr[i], i]);
}
}
// Finding the previous greater element of the array.
function makePrev(arr, n, prevBig)
{
var s = [];
for (var i = 0; i < n; i++) {
prevBig[i] = -1;
while (s.length!=0 && s[s.length-1][0] < arr[i])
s.pop();
if (s.length!=0)
prevBig[i] = s[s.length-1][1];
s.push([arr[i], i]);
}
}
// Wrapper Function
function wrapper( arr, n)
{
var nextBig = Array(MAXN).fill(0);
var prevBig= Array(MAXN).fill(0);
var maxi= Array(MAXN).fill(0);
var ans = 0;
// Finding previous largest element
makePrev(arr, n, prevBig);
// Finding next largest element
makeNext(arr, n, nextBig);
for (var i = 0; i < n; i++)
if (nextBig[i] != i)
maxi[nextBig[i] - i] = Math.max(maxi[nextBig[i] - i],
i - prevBig[i]);
for (var i = 0; i < n; i++)
ans += maxi[i];
return ans;
}
// Driven Program
var arr = [1, 3, 2, 4];
var n = arr.length;
document.write( wrapper(arr, n));
</script>
3
Análisis de Complejidad:
- Complejidad de tiempo: O(n)
- Complejidad espacial: O(n) en el peor de los casos.
Este artículo es una contribución de anuj0503 . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geekforgeeks.org o envíe su 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