Dada una array arr[] de tamaño N. La tarea es verificar si la array tiene 3 elementos en los índices i , j y k tales que i < j < k y arr[i] < arr[j] > arr[k] y arr[i] < arr[k] .
Ejemplos:
Entrada: N = 6, arr[] = {4, 7, 11, 5, 13, 2}
Salida: Verdadero
Explicación: [4, 7, 5] cumple la condición.Entrada: N = 4, arr[] = {11, 11, 12, 9}
Salida: Falso
Explicación: No hay 3 elementos que se ajusten a la condición dada.
Enfoque: El problema se puede resolver utilizando la siguiente idea:
Atraviese la array de N-1 a 0 y verifique para cada i -ésimo elemento si el elemento más grande a la derecha que es más pequeño que el i -ésimo elemento es mayor que el elemento más pequeño a la izquierda de i , entonces es verdadero, de lo contrario, es falso.
Para encontrar el elemento mayor más pequeño que el i -ésimo elemento, podemos usar el siguiente elemento mayor
Siga los pasos mencionados a continuación para implementar la idea:
- Crea un vector pequeño[] .
- Recorra la array arr[] y mantenga un valor mínimo que sea el valor más pequeño de arr[0, . . ., i].
- Si no hay ningún elemento más pequeño que Arr[i] store -1 else store min .
- Inicialice una pila vacía (digamos S ). Runa bucle de N-1 a 0 :
- Si la pila no está vacía y el elemento superior en la pila <= pequeño[i], extraiga el elemento;
- Si la pila no está vacía y es pequeña[i] <elemento superior en la pila <arr[i], devuelve verdadero.
- De lo contrario, inserte arr[i] en la pila.
- Si la condición no se cumple, devuelve falso .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find if the pattern exist
bool recreationalSpot(int arr[], int n)
{
vector<int> small;
// min1 is used to keep track of minimum
// element from 0th index to current index
int min1 = arr[0];
for (int i = 0; i < n; i++) {
if (min1 >= arr[i]) {
min1 = arr[i];
// If the element itself is smaller than
// all the elements on left side
// then we push -1
small.push_back(-1);
}
else {
// Push that min1;
small.push_back(min1);
}
}
// Initialise empty stack
stack<int> s;
// Looping from last index to first index
// don't consider the possibility of 0th index
// because it does't have left elements
for (int i = n - 1; i > 0; i--) {
// Pops up until either stack is empty or
// top element greater than small[i]
while (!s.empty() && s.top() <= small[i]) {
s.pop();
}
// Checks the condiitons that top element
// of stack is less than arr[i]
// If true return true;
if (!s.empty() && small[i] != -1
&& s.top() < arr[i])
return true;
s.push(arr[i]);
}
return false;
}
// Driver Code
int main()
{
int arr[] = { 4, 7, 11, 5, 13, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
if (recreationalSpot(arr, N)) {
cout << "True";
}
else {
cout << "False";
}
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find if the pattern exist
static boolean recreationalSpot(int[] arr, int n)
{
List<Integer> small = new ArrayList<>();
// min1 is used to keep track of minimum element
// from 0th index to current index
int min1 = arr[0];
for (int i = 0; i < n; i++) {
if (min1 >= arr[i]) {
min1 = arr[i];
// If the element itself is smaller than all
// the elements on left side then we push
// -1.
small.add(-1);
}
else {
// Add that min1;
small.add(min1);
}
}
// Initialize empty stack
Stack<Integer> s = new Stack<>();
// Looping from last index to first index don't
// consider the possibility of 0th index because it
// doesn't have left elements
for (int i = n - 1; i > 0; i--) {
// Pop's up until either stack is empty or top
// element greater than small[i]
while (!s.isEmpty()
&& s.peek() <= small.get(i)) {
s.pop();
}
// Checks the conditions that top element of
// stack is less than arr[i] If true, then
// return true;
if (!s.isEmpty() && small.get(i) != -1
&& s.peek() < arr[i]) {
return true;
}
s.push(arr[i]);
}
return false;
}
public static void main(String[] args)
{
int[] arr = { 4, 7, 11, 5, 13, 2 };
int N = arr.length;
// Function call
if (recreationalSpot(arr, N)) {
System.out.print("True");
}
else {
System.out.print("False");
}
}
}
// This code is contributed by lokeshmvs21.
Python3
# Python3 code to implement the above approach
# Function to find if the pattern exist
def recreationalSpot(arr, n) :
small = [];
# min1 is used to keep track of minimum
# element from 0th index to current index
min1 = arr[0];
for i in range(n) :
if (min1 >= arr[i]) :
min1 = arr[i];
# If the element itself is smaller than
# all the elements on left side
# then we push -1
small.append(-1);
else :
# Push that min1;
small.append(min1);
# Initialise empty stack
s = [];
# Looping from last index to first index
# don't consider the possibility of 0th index
# because it does't have left elements
for i in range(n - 1, 0, -1) :
# Pops up until either stack is empty or
# top element greater than small[i]
while (len(s) != 0 and s[-1] <= small[i]) :
s.pop();
# Checks the condiitons that top element
# of stack is less than arr[i]
# If true return true;
if (len(s) != 0 and small[i] != -1 and s[-1] < arr[i]) :
return True;
s.append(arr[i]);
return False;
# Driver Code
if __name__ == "__main__" :
arr = [ 4, 7, 11, 5, 13, 2 ];
N = len(arr);
# Function Call
if (recreationalSpot(arr, N)) :
print("True");
else :
print("False");
# This code is contributed by AnkThon
Producción
True
Complejidad temporal: O(N).
Espacio Auxiliar: O(N).