Dado un arreglo A[] de N enteros, la tarea es encontrar el rango relativo para cada elemento en el arreglo dado.
El rango relativo para cada elemento de la array es el recuento de elementos que es mayor que el elemento actual en la subsecuencia creciente más larga del elemento actual.
Ejemplos:
Entrada: A[] = {8, 16, 5, 6, 9}, N = 5
Salida: {1, 0, 2, 1, 0}
Explicación:
Para i = 0, la secuencia requerida es {8, 16} Relativa Rango = 1.
Para i = 1, dado que todos los elementos después de 16 son menores que 16, Rango relativo = 0.
Para i = 2, la secuencia requerida es {5, 6, 9} Rango relativo = 2
Para i = 3, la secuencia requerida es {6, 9} Rango relativo = 1
Para i = 4, la secuencia requerida es {9} Rango relativo = 0Entrada: A[] = {1, 2, 3, 5, 4}
Salida: {3, 2, 1, 0, 0}
Explicación:
Para i = 0, la secuencia requerida es {1, 2, 3, 5}, Rango relativo = 3
Para i = 1, la secuencia requerida es {2, 3, 5}, Rango relativo = 2
Para i = 2, la secuencia requerida es {3, 5}, Rango relativo = 1
Para i = 3, la secuencia requerida es {5}, rango relativo = 0
Para i = 4, la secuencia requerida es {4}, rango relativo = 0
Enfoque ingenuo: la idea es generar la subsecuencia creciente más larga para cada elemento y luego, el rango relativo para cada elemento es (longitud de LIS – 1) .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar una pila y almacenar los elementos en orden no decreciente desde la derecha hasta cada elemento (digamos A[i] ), luego el rango para cada A[i] es el (tamaño de la pila – 1) hasta ese elemento. A continuación se muestra la ilustración del mismo:
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 find relative rank for
// each element in the array A[]
void findRank(int A[], int N)
{
// Create Rank Array
int rank[N] = {};
// Stack to store numbers in
// non-decreasing order from right
stack<int> s;
// Push last element in stack
s.push(A[N - 1]);
// Iterate from second last
// element to first element
for (int i = N - 2; i >= 0; i--) {
// If current element is less
// than the top of stack and
// push A[i] in stack
if (A[i] < s.top()) {
s.push(A[i]);
// Rank is stack size - 1
// for current element
rank[i] = s.size() - 1;
}
else {
// Pop elements from stack
// till current element is
// greater than the top
while (!s.empty()
&& A[i] >= s.top()) {
s.pop();
}
// Push current element in Stack
s.push(A[i]);
// Rank is stack size - 1
rank[i] = s.size() - 1;
}
}
// Print rank of all elements
for (int i = 0; i < N; i++) {
cout << rank[i] << " ";
}
}
// Driver Code
int main()
{
// Given array A[]
int A[] = { 1, 2, 3, 5, 4 };
int N = sizeof(A) / sizeof(A[0]);
// Function call
findRank(A, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
import java.lang.*;
class GFG{
// Function to find relative rank for
// each element in the array A[]
static void findRank(int[] A, int N)
{
// Create Rank Array
int[] rank = new int[N];
// Stack to store numbers in
// non-decreasing order from right
Stack<Integer> s = new Stack<Integer>();
// Push last element in stack
s.add(A[N - 1]);
// Iterate from second last
// element to first element
for(int i = N - 2; i >= 0; i--)
{
// If current element is less
// than the top of stack and
// push A[i] in stack
if (A[i] < s.peek())
{
s.add(A[i]);
// Rank is stack size - 1
// for current element
rank[i] = s.size() - 1;
}
else
{
// Pop elements from stack
// till current element is
// greater than the top
while (!s.isEmpty() &&
A[i] >= s.peek())
{
s.pop();
}
// Push current element in Stack
s.add(A[i]);
// Rank is stack size - 1
rank[i] = s.size() - 1;
}
}
// Print rank of all elements
for(int i = 0; i < N; i++)
{
System.out.print(rank[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array A[]
int A[] = { 1, 2, 3, 5, 4 };
int N = A.length;
// Function call
findRank(A, N);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to find relative rank for # each element in the array A[] def findRank(A, N): # Create Rank Array rank = [0] * N # Stack to store numbers in # non-decreasing order from right s = [] # Push last element in stack s.append(A[N - 1]) # Iterate from second last # element to first element for i in range(N - 2, -1, -1): # If current element is less # than the top of stack and # append A[i] in stack if (A[i] < s[-1]): s.append(A[i]) # Rank is stack size - 1 # for current element rank[i] = len(s) - 1 else: # Pop elements from stack # till current element is # greater than the top while (len(s) > 0 and A[i] >= s[-1]): del s[-1] # Push current element in Stack s.append(A[i]) # Rank is stack size - 1 rank[i] = len(s) - 1 # Print rank of all elements for i in range(N): print(rank[i], end = " ") # Driver Code if __name__ == '__main__': # Given array A[] A = [ 1, 2, 3, 5, 4 ] N = len(A) # Function call findRank(A, N) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG{
// Function to find relative rank for
// each element in the array A[]
static void findRank(int[] A, int N)
{
// Create Rank Array
int[] rank = new int[N];
// Stack to store numbers in
// non-decreasing order from right
Stack<int> s = new Stack<int>();
// Push last element in stack
s.Push(A[N - 1]);
// Iterate from second last
// element to first element
for(int i = N - 2; i >= 0; i--)
{
// If current element is less
// than the top of stack and
// push A[i] in stack
if (A[i] < s.Peek())
{
s.Push(A[i]);
// Rank is stack size - 1
// for current element
rank[i] = s.Count() - 1;
}
else
{
// Pop elements from stack
// till current element is
// greater than the top
while (s.Count() != 0 &&
A[i] >= s.Peek())
{
s.Pop();
}
// Push current element in Stack
s.Push(A[i]);
// Rank is stack size - 1
rank[i] = s.Count() - 1;
}
}
// Print rank of all elements
for(int i = 0; i < N; i++)
{
Console.Write(rank[i] + " ");
}
}
// Driver Code
public static void Main()
{
// Given array A[]
int[] A = new int[] { 1, 2, 3, 5, 4 };
int N = A.Length;
// Function call
findRank(A, N);
}
}
// This code is contributed by sanjoy_62
3 2 1 0 0
Complejidad temporal: O(N)
Espacio auxiliar: O(1)