Dada una array arr[] que consta de N enteros, donde cada elemento de la array representa la altura de un edificio situado en las coordenadas X , la tarea es verificar si es posible seleccionar 3 edificios, de modo que el tercer edificio seleccionado sea más alto que el primer edificio seleccionado y más bajo que el segundo edificio seleccionado.
Ejemplos:
Entrada: arr[] = {4, 7, 11, 5, 13, 2}
Salida: Sí
Explicación:
Una forma posible es seleccionar el edificio en los índices [0, 1, 3] con alturas 4, 7 y 5 respectivamente.Entrada: arr[] = {11, 11, 12, 9}
Salida: No
Enfoque: el problema dado se puede resolver utilizando la estructura de datos Stack . Siga los pasos a continuación para resolver el problema:
- Si N es menor que 3 , imprima “ No ”.
- Inicialice una array, digamos preMin[], para almacenar la array mínima de prefijo de la array arr[].
- Recorra la array arr[] y actualice preMin[i] como preMin[i] = min(preMin[i-1], arr[i]).
- Ahora, inicialice un Stack, digamos stack, para almacenar los elementos desde el final en orden ascendente.
- Recorra la array arr[] en reversa usando una variable, digamos i, y realice los siguientes pasos:
- Si arr[i] es mayor que preMin[i] , haga lo siguiente:
- Iterar mientras la pila no está vacía y el elemento superior de la pila es menor que preMin[i], luego extraer el elemento superior de la pila en cada iteración.
- Si la pila no está vacía y el elemento superior de la pila es menor que el arr[i], imprima » Sí » y regrese.
- De lo contrario, después del paso anterior, inserte arr[i] en la pila .
- Si arr[i] es mayor que preMin[i] , haga lo siguiente:
- Después de completar los pasos anteriores, si ninguno de los casos anteriores satisface, imprima » No «.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to check if it is possible // to select three buildings that // satisfy the given condition string recreationalSpot(int arr[], int N) { if (N < 3) { return "No"; } // Stores prefix min array int preMin[N]; preMin[0] = arr[0]; // Iterate over the range [1, N-1] for (int i = 1; i < N; i++) { preMin[i] = min(preMin[i - 1], arr[i]); } // Stores the element from the // ending in increasing order stack<int> stack; // Iterate until j is greater than // or equal to 0 for (int j = N - 1; j >= 0; j--) { // If current array element is // greater than the prefix min // upto j if (arr[j] > preMin[j]) { // Iterate while stack is not // empty and top element is // less than or equal to preMin[j] while (!stack.empty() && stack.top() <= preMin[j]) { // Remove the top element stack.pop(); } // If stack is not empty and top // element of the stack is less // than the current element if (!stack.empty() && stack.top() < arr[j]) { return "Yes"; } // Push the arr[j] in stack stack.push(arr[j]); } } // If none of the above case // satisfy then return "No" return "No"; } // Driver code int main() { // Input int arr[] = { 4, 7, 11, 5, 13, 2 }; int size = sizeof(arr) / sizeof(arr[0]); cout << recreationalSpot(arr, size); }
Java
// Java implementation of the above approach import java.io.*; import java.util.*; class GFG{ // Function to check if it is possible // to select three buildings that // satisfy the given condition static String recreationalSpot(int arr[], int N) { if (N < 3) { return "No"; } // Stores prefix min array int preMin[] = new int[N]; preMin[0] = arr[0]; // Iterate over the range [1, N-1] for(int i = 1; i < N; i++) { preMin[i] = Math.min(preMin[i - 1], arr[i]); } // Stores the element from the // ending in increasing order Stack<Integer> stack = new Stack<Integer>(); // Iterate until j is greater than // or equal to 0 for(int j = N - 1; j >= 0; j--) { // If current array element is // greater than the prefix min // upto j if (arr[j] > preMin[j]) { // Iterate while stack is not // empty and top element is // less than or equal to preMin[j] while (stack.empty() == false && stack.peek() <= preMin[j]) { // Remove the top element stack.pop(); } // If stack is not empty and top // element of the stack is less // than the current element if (stack.empty() == false && stack.peek() < arr[j]) { return "Yes"; } // Push the arr[j] in stack stack.push(arr[j]); } } // If none of the above case // satisfy then return "No" return "No"; } // Driver code public static void main(String[] args) { // Input int arr[] = { 4, 7, 11, 5, 13, 2 }; int size = arr.length; System.out.println(recreationalSpot(arr, size)); } } // This code is contributed by Dharanendra L V.
Python3
# Python3 implementation of the above approach # Function to check if it is possible # to select three buildings that # satisfy the given condition def recreationalSpot(arr, N): if (N < 3): return "No" # Stores prefix min array preMin = [0] * N preMin[0] = arr[0] # Iterate over the range [1, N-1] for i in range(1, N): preMin[i] = min(preMin[i - 1], arr[i]) # Stores the element from the # ending in increasing order stack = [] # Iterate until j is greater than # or equal to 0 for j in range(N - 1, -1, -1): # If current array element is # greater than the prefix min # upto j if (arr[j] > preMin[j]): # Iterate while stack is not # empty and top element is # less than or equal to preMin[j] while (len(stack) > 0 and stack[-1] <= preMin[j]): # Remove the top element del stack[-1] # If stack is not empty and top # element of the stack is less # than the current element if (len(stack) > 0 and stack[-1] < arr[j]): return "Yes" # Push the arr[j] in stack stack.append(arr[j]) # If none of the above case # satisfy then return "No" return "No" # Driver code if __name__ == '__main__': # Input arr = [ 4, 7, 11, 5, 13, 2 ] size = len(arr) print (recreationalSpot(arr, size)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach using System; using System.Collections.Generic; public class GFG{ // Function to check if it is possible // to select three buildings that // satisfy the given condition static String recreationalSpot(int []arr, int N) { if (N < 3) { return "No"; } // Stores prefix min array int []preMin = new int[N]; preMin[0] = arr[0]; // Iterate over the range [1, N-1] for(int i = 1; i < N; i++) { preMin[i] = Math.Min(preMin[i - 1], arr[i]); } // Stores the element from the // ending in increasing order Stack<int> stack = new Stack<int>(); // Iterate until j is greater than // or equal to 0 for(int j = N - 1; j >= 0; j--) { // If current array element is // greater than the prefix min // upto j if (arr[j] > preMin[j]) { // Iterate while stack is not // empty and top element is // less than or equal to preMin[j] while (stack.Count!=0 && stack.Peek() <= preMin[j]) { // Remove the top element stack.Pop(); } // If stack is not empty and top // element of the stack is less // than the current element if (stack.Count!=0 && stack.Peek() < arr[j]) { return "Yes"; } // Push the arr[j] in stack stack.Push(arr[j]); } } // If none of the above case // satisfy then return "No" return "No"; } // Driver code public static void Main(String[] args) { // Input int []arr = { 4, 7, 11, 5, 13, 2 }; int size = arr.Length; Console.WriteLine(recreationalSpot(arr, size)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript implementation of the above approach // Function to check if it is possible // to select three buildings that // satisfy the given condition function recreationalSpot(arr, N) { if (N < 3) { return "No"; } // Stores prefix min array var preMin = new Array(N); preMin[0] = arr[0]; var i; // Iterate over the range [1, N-1] for (i = 1; i < N; i++) { preMin[i] = Math.min(preMin[i - 1], arr[i]); } // Stores the element from the // ending in increasing order var st = []; var j; // Iterate until j is greater than // or equal to 0 for (j = N - 1; j >= 0; j--) { // If current array element is // greater than the prefix min // upto j if (arr[j] > preMin[j]) { // Iterate while st is not // empty and top element is // less than or equal to preMin[j] while (st.length>0 && st[st.length-1] <= preMin[j]) { // Remove the top element st.pop(); } // If st is not empty and top // element of the st is less // than the current element if (st.length>0 && st[st.length-1] < arr[j]) { return "Yes"; } // Push the arr[j] in st st.push(arr[j]); } } // If none of the above case // satisfy then return "No" return "No"; } // Driver code // Input var arr = [4, 7, 11, 5, 13, 2]; var size = arr.length; document.write(recreationalSpot(arr, size)); </script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por nareshsaharan1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA