Encuentra si un subarreglo tiene forma de montaña o no

Posted on by Rudeus Greyrat

Nos dan una array de números enteros y un rango, necesitamos encontrar si el subarreglo que cae en este rango tiene valores en forma de montaña o no. Se dice que todos los valores del subarreglo tienen la forma de una montaña si todos los valores aumentan o disminuyen o primero aumentan y luego disminuyen. 
Más formalmente, se dice que un subarreglo [a1, a2, a3 … aN] tiene forma de montaña si existe un número entero K, 1 <= K <= N tal que, 
a1 <= a2 <= a3 .. <= aK >= a(K+1) >= a(K+2) …. >= unN 

Ejemplos: 

Input : Arr[]  = [2 3 2 4 4 6 3 2], Range = [0, 2]
Output :  Yes

Explanation: The output is yes , subarray is [2 3 2], 
so subarray first increases and then decreases

Input:  Arr[] = [2 3 2 4 4 6 3 2], Range = [2, 7]
Output: Yes

Explanation: The output is yes , subarray is [2 4 4 6 3 2], 
so subarray first increases and then decreases


Input: Arr[]= [2 3 2 4 4 6 3 2], Range = [1, 3]
Output: no

Explanation: The output is no, subarray is [3 2 4], 
so subarray is not in the form above stated

Solución: 

  • Enfoque: el problema tiene múltiples consultas, por lo que para cada consulta, la solución debe calcularse con la menor complejidad de tiempo posible. Así que crea dos espacios adicionales de la longitud de la array original. Para cada elemento, encuentre el último índice en el lado izquierdo que está aumentando, es decir, mayor que su elemento anterior y encuentre el elemento en el lado derecho almacenará el primer índice en el lado derecho que está disminuyendo, es decir, mayor que su siguiente elemento. Si estos valores se pueden calcular para cada índice en tiempo constante, entonces para cada rango dado, la respuesta se puede dar en tiempo constante.
  • Algoritmo: 
    1. Cree dos espacios adicionales de longitud n , izquierda y derecha y una variable adicional lastptr
    2. Inicializar left[0] = 0 y lastptr = 0
    3. Atraviesa la array original desde el segundo índice hasta el final
    4. Para cada índice, verifique si es mayor que el elemento anterior, si es así, actualice el último punto con el índice actual.
    5. Para cada índice, almacene el último punto en la izquierda [i]
    6. inicializar a la derecha [N-1] = N-1 y lastptr = N-1
    7. Atraviesa la array original desde el penúltimo índice hasta el inicio
    8. Para cada índice, verifique si es mayor que el siguiente elemento, si es así, actualice el último punto con el índice actual.
    9. Para cada índice, almacene el lastptr en right[i]
    10. Ahora procesa las consultas.
    11. para cada consulta l, r , si derecha[l] >= izquierda[r] entonces imprima sí , de lo contrario, no
  • Implementación:

C++

// C++ program to check whether a subarray is in
// mountain form or not
#include <bits/stdc++.h>
using namespace std;
 
// Utility method to construct left and right array
int preprocess(int arr[], int N, int left[], int right[])
{
    // Initialize first left index as that index only
    left[0] = 0;
    int lastIncr = 0;
 
    for (int i = 1; i < N; i++)
    {
        // if current value is greater than previous,
        // update last increasing
        if (arr[i] > arr[i - 1])
            lastIncr = i;
        left[i] = lastIncr;
    }
 
    // Initialize last right index as that index only
    right[N - 1] = N - 1;
    int firstDecr = N - 1;
 
    for (int i = N - 2; i >= 0; i--)
    {
        // if current value is greater than next,
        // update first decreasing
        if (arr[i] > arr[i + 1])
            firstDecr = i;
        right[i] = firstDecr;
    }
}
 
// Method returns true if arr[L..R] is in mountain form
bool isSubarrayMountainForm(int arr[], int left[],
                             int right[], int L, int R)
{
    // return true only if right at starting range is
    // greater than left at ending range
    return (right[L] >= left[R]);
}
 
//    Driver code to test above methods
int main()
{
    int arr[] = {2, 3, 2, 4, 4, 6, 3, 2};
    int N = sizeof(arr) / sizeof(int);
 
    int left[N], right[N];
    preprocess(arr, N, left, right);
 
    int L = 0;
    int R = 2;
    if (isSubarrayMountainForm(arr, left, right, L, R))
        cout << "Subarray is in mountain form\n";
    else
        cout << "Subarray is not in mountain form\n";
 
    L = 1;
    R = 3;
    if (isSubarrayMountainForm(arr, left, right, L, R))
        cout << "Subarray is in mountain form\n";
    else
        cout << "Subarray is not in mountain form\n";
 
    return 0;
}

Java

// Java program to check whether a subarray is in
// mountain form or not
class SubArray
{
    // Utility method to construct left and right array
    static void preprocess(int arr[], int N, int left[], int right[])
    {
        // initialize first left index as that index only
        left[0] = 0;
        int lastIncr = 0;
     
        for (int i = 1; i < N; i++)
        {
            // if current value is greater than previous,
            // update last increasing
            if (arr[i] > arr[i - 1])
                    lastIncr = i;
            left[i] = lastIncr;
        }
     
        // initialize last right index as that index only
        right[N - 1] = N - 1;
        int firstDecr = N - 1;
     
        for (int i = N - 2; i >= 0; i--)
        {
            // if current value is greater than next,
            // update first decreasing
            if (arr[i] > arr[i + 1])
                    firstDecr = i;
            right[i] = firstDecr;
        }
    }
     
    // method returns true if arr[L..R] is in mountain form
    static boolean isSubarrayMountainForm(int arr[], int left[],
                                    int right[], int L, int R)
    {
        // return true only if right at starting range is
        // greater than left at ending range
        return (right[L] >= left[R]);
    }
     
    public static void main(String[] args)
    {
        int arr[] = {2, 3, 2, 4, 4, 6, 3, 2};
        int N = arr.length;
        int left[] = new int[N];
        int right[] = new int[N];
        preprocess(arr, N, left, right);
        int L = 0;
        int R = 2;
         
        if (isSubarrayMountainForm(arr, left, right, L, R))
            System.out.println("Subarray is in mountain form");
        else
            System.out.println("Subarray is not in mountain form");
     
        L = 1;
        R = 3;
     
        if (isSubarrayMountainForm(arr, left, right, L, R))
            System.out.println("Subarray is in mountain form");
        else
            System.out.println("Subarray is not in mountain form");
    }
}
// This Code is Contributed by Saket Kumar

Python3

# Python 3 program to check whether a subarray is in
# mountain form or not
 
# Utility method to construct left and right array
def preprocess(arr, N, left, right):
    # initialize first left index as that index only
    left[0] = 0
    lastIncr = 0
 
    for i in range(1,N):
        # if current value is greater than previous,
        # update last increasing
        if (arr[i] > arr[i - 1]):
            lastIncr = i
        left[i] = lastIncr
 
    # initialize last right index as that index only
    right[N - 1] = N - 1
    firstDecr = N - 1
 
    i = N - 2
    while(i >= 0):
        # if current value is greater than next,
        # update first decreasing
        if (arr[i] > arr[i + 1]):
            firstDecr = i
        right[i] = firstDecr
        i -= 1
 
# method returns true if arr[L..R] is in mountain form
def isSubarrayMountainForm(arr, left, right, L, R):
     
    # return true only if right at starting range is
    # greater than left at ending range
    return (right[L] >= left[R])
 
# Driver code
if __name__ == '__main__':
    arr = [2, 3, 2, 4, 4, 6, 3, 2]
    N = len(arr)
 
    left = [0 for i in range(N)]
    right = [0 for i in range(N)]
    preprocess(arr, N, left, right)
 
    L = 0
    R = 2
    if (isSubarrayMountainForm(arr, left, right, L, R)):
        print("Subarray is in mountain form")
    else:
        print("Subarray is not in mountain form")
 
    L = 1
    R = 3
    if (isSubarrayMountainForm(arr, left, right, L, R)):
        print("Subarray is in mountain form")
    else:
        print("Subarray is not in mountain form")
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to check whether
// a subarray is in mountain
// form or not
using System;
 
class GFG
{
     
    // Utility method to construct
    // left and right array
    static void preprocess(int []arr, int N,
                           int []left, int []right)
    {
        // initialize first left
        // index as that index only
        left[0] = 0;
        int lastIncr = 0;
     
        for (int i = 1; i < N; i++)
        {
            // if current value is
            // greater than previous,
            // update last increasing
            if (arr[i] > arr[i - 1])
                    lastIncr = i;
            left[i] = lastIncr;
        }
     
        // initialize last right
        // index as that index only
        right[N - 1] = N - 1;
        int firstDecr = N - 1;
     
        for (int i = N - 2; i >= 0; i--)
        {
            // if current value is
            // greater than next,
            // update first decreasing
            if (arr[i] > arr[i + 1])
                    firstDecr = i;
            right[i] = firstDecr;
        }
    }
     
    // method returns true if
    // arr[L..R] is in mountain form
    static bool isSubarrayMountainForm(int []arr, int []left,
                                       int []right, int L, int R)
    {
        // return true only if right at
        // starting range is greater
        // than left at ending range
        return (right[L] >= left[R]);
    }
     
     
    // Driver Code
    static public void Main ()
    {
        int []arr = {2, 3, 2, 4,
                     4, 6, 3, 2};
        int N = arr.Length;
        int []left = new int[N];
        int []right = new int[N];
        preprocess(arr, N, left, right);
         
        int L = 0;
        int R = 2;
         
        if (isSubarrayMountainForm(arr, left,
                                   right, L, R))
            Console.WriteLine("Subarray is in " +
                                "mountain form");
        else
            Console.WriteLine("Subarray is not " +
                              "in mountain form");
     
        L = 1;
        R = 3;
     
        if (isSubarrayMountainForm(arr, left,
                                   right, L, R))
            Console.WriteLine("Subarray is in " +
                                "mountain form");
        else
            Console.WriteLine("Subarray is not " +
                              "in mountain form");
    }
}
 
// This code is contributed by aj_36

Javascript

<script>
    // Javascript program to check whether
    // a subarray is in mountain
    // form or not
     
    // Utility method to construct
    // left and right array
    function preprocess(arr, N, left, right)
    {
        // initialize first left
        // index as that index only
        left[0] = 0;
        let lastIncr = 0;
       
        for (let i = 1; i < N; i++)
        {
            // if current value is
            // greater than previous,
            // update last increasing
            if (arr[i] > arr[i - 1])
                    lastIncr = i;
            left[i] = lastIncr;
        }
       
        // initialize last right
        // index as that index only
        right[N - 1] = N - 1;
        let firstDecr = N - 1;
       
        for (let i = N - 2; i >= 0; i--)
        {
            // if current value is
            // greater than next,
            // update first decreasing
            if (arr[i] > arr[i + 1])
                    firstDecr = i;
            right[i] = firstDecr;
        }
    }
       
    // method returns true if
    // arr[L..R] is in mountain form
    function isSubarrayMountainForm(arr, left, right, L, R)
    {
        // return true only if right at
        // starting range is greater
        // than left at ending range
        return (right[L] >= left[R]);
    }
     
    let arr = [2, 3, 2, 4, 4, 6, 3, 2];
    let N = arr.length;
    let left = new Array(N);
    let right = new Array(N);
    preprocess(arr, N, left, right);
 
    let L = 0;
    let R = 2;
 
    if (isSubarrayMountainForm(arr, left, right, L, R))
      document.write("Subarray is in " + "mountain form" + "</br>");
    else
      document.write("Subarray is not " + "in mountain form" + "</br>");
 
    L = 1;
    R = 3;
 
    if (isSubarrayMountainForm(arr, left, right, L, R))
      document.write("Subarray is in " + "mountain form");
    else
      document.write("Subarray is not " + "in mountain form");
     
</script>
  • Producción:
Subarray is in mountain form
Subarray is not in mountain form
  • Análisis de Complejidad: 
    • Complejidad temporal: O(n). 
      Solo se necesitan dos recorridos, por lo que la complejidad del tiempo es O (n).
    • Complejidad espacial: O(n). 
      Se requieren dos espacios adicionales de longitud n, por lo que la complejidad del espacio es O(n).

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *