Рубрики

Найдите, находится ли подрешетка в форме горы или нет

Нам дан массив целых чисел и диапазон, нам нужно выяснить, имеет ли подрешетка, попадающая в этот диапазон, значения в виде горы или нет. Говорят, что все значения подмассива имеют форму горы, если либо все значения увеличиваются или уменьшаются, либо сначала увеличиваются, а затем уменьшаются.
Говорят, что более формально подрешетка [a1, a2, a3… aN] имеет форму горы, если существует целое число K, 1 <= K <= N, такое, что
a1 <= a2 <= a3 .. <= aK> = a (K + 1)> = a (K + 2)…. > = aN
Примеры:

Arr[]  = [2 3 2 4 4 6 3 2]
Range = [0, 2]
Output yes because [2 3 2] subarray first 
increases and then decreases

Range = [2, 7]
Output yes because [2 4 4 6 3 2] subarray 
first increases and then decreases

Range = [2, 3]
Output yes because [2 4] subarray increases

Range = [1, 3]
Output no because [3 2 4] is not in the form 
above stated

Мы можем решить эту проблему, сначала выполнив некоторую предварительную обработку, затем мы можем ответить для каждого подмассива за постоянное количество времени. Мы сохраняем два массива влево и вправо, где left [i] хранит последний индекс с левой стороны, который увеличивается, т.е. больше, чем его предыдущий элемент, а right [i] будет хранить первый индекс с правой стороны, который уменьшается, т.е. больше, чем его следующий элемент. После того, как мы сохранили эти массивы, мы можем отвечать на каждый подмассив в постоянном времени. Предположим, что диапазон [l, r] задается тогда, только если справа [l]> = left [r], подрешетка будет в форме горы, иначе не потому, что должен прийти первый индекс в убывающей форме (то есть справа [l]) позже, чем последний индекс в возрастающей форме (т.е. оставил [r]).
Эта процедура демонстрируется для приведенного выше примера массива.

Arr[] = [2 3 2 4 4 6 3 2]
Using above procedure building left and right array,
left[]   =  [0 1 1 3 3 5 5 5]
right[] =  [1 1 5 5 5 5 6 7]
Range = [2, 4]
Now right[2] is 5 and left[4] is 3 that means at
index 2 first decreasing element is right to the 
last increasing element at index 4, so they should
have a mountain form.

Range = [0, 3]
Now right[0] is 1 and left[3] is 3 that means at
index 0 first decreasing element is left to the 
last increasing element at index 3, so the subarray 
corresponding to this range does not have mountain 
form.  We can see this in the array itself, right[0]
is 1 which is value 3 and left[3] is 3 which is 
value 4 so 4 which is in increasing form (due to 
previous value 2) comes later to 3 which is in 
decreasing form (due to next value 2), mountain form
was not possible here, same information is carried 
out with the help of left and right array.

Вспомогательное пространство для этого решения — O (N), а предварительная обработка занимает время O (N), после чего каждый подрешетку можно обрабатывать в постоянное время.

C / C ++

// C ++ программа для проверки наличия подмассива
// горная форма или нет
#include <bits/stdc++.h>

using namespace std;

  
// Служебный метод для построения левого и правого массива

int preprocess(int arr[], int N, int left[], int right[])

{

    // инициализируем первый левый индекс только как этот индекс

    left[0] = 0;

    int lastIncr = 0;

  

    for (int i = 1; i < N; i++)

    {

        // если текущее значение больше предыдущего,

        // обновляем последнее увеличение

        if (arr[i] > arr[i - 1])

            lastIncr = i;

        left[i] = lastIncr;

    }

  

    // инициализируем последний правый индекс только как этот индекс

    right[N - 1] = N - 1;

    int firstDecr = N - 1;

  

    for (int i = N - 2; i >= 0; i--)

    {

        // если текущее значение больше следующего,

        // обновляем первый убывающий

        if (arr[i] > arr[i + 1])

            firstDecr = i;

        right[i] = firstDecr;

    }

}

  
// метод возвращает true, если arr [L..R] находится в форме горы

bool isSubarrayMountainForm(int arr[], int left[],

                             int right[], int L, int R)

{

    // возвращаем true только если прямо в начальном диапазоне

    // больше левого в конце диапазона

    return (right[L] >= left[R]);

}

  
// Код драйвера для тестирования вышеуказанных методов

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-программа для проверки наличия подмассива
// горная форма или нет

class SubArray

{

    // Служебный метод для построения левого и правого массива

    static void preprocess(int arr[], int N, int left[], int right[])

    {

        // инициализируем первый левый индекс только как этот индекс

        left[0] = 0;

        int lastIncr = 0;

      

        for (int i = 1; i < N; i++)

        {

            // если текущее значение больше предыдущего,

            // обновляем последнее увеличение

            if (arr[i] > arr[i - 1])

                    lastIncr = i;

            left[i] = lastIncr;

        }

      

        // инициализируем последний правый индекс только как этот индекс

        right[N - 1] = N - 1;

        int firstDecr = N - 1;

      

        for (int i = N - 2; i >= 0; i--)

        {

            // если текущее значение больше следующего,

            // обновляем первый убывающий

            if (arr[i] > arr[i + 1])

                    firstDecr = i;

            right[i] = firstDecr;

        }

    }

      

    // метод возвращает true, если arr [L..R] находится в форме горы

    static boolean isSubarrayMountainForm(int arr[], int left[],

                                    int right[], int L, int R)

    {

        // возвращаем true только если прямо в начальном диапазоне

        // больше левого в конце диапазона

        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");

    }

}
// Этот код предоставлен Сакет Кумар

python3

# Программа Python 3 для проверки наличия подмассива
# горная форма или нет

  
# Служебный метод для построения левого и правого массива

def preprocess(arr, N, left, right):

    # инициализировать первый левый индекс только как этот индекс

    left[0] = 0

    lastIncr = 0

  

    for i in range(1,N):

        # если текущее значение больше предыдущего,

        # обновление последнего увеличения

        if (arr[i] > arr[i - 1]):

            lastIncr = i

        left[i] = lastIncr

  

    # инициализировать последний правильный индекс только как этот индекс

    right[N - 1] = N - 1

    firstDecr = N - 1

  

    i = N - 2

    while(i >= 0):

        # если текущее значение больше следующего,

        # обновить сначала по убыванию

        if (arr[i] > arr[i + 1]):

            firstDecr = i

        right[i] = firstDecr

        i -= 1

  
# метод возвращает true, если arr [L..R] находится в форме горы

def isSubarrayMountainForm(arr, left, right, L, R):

      

    # возвращает true, только если прямо в начальном диапазоне

    # больше, чем осталось в конце диапазона

    return (right[L] >= left[R])

  
# Код драйвера

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")

  
# Этот код предоставлен
# Surendra_Gangwar

C #

// C # программа для проверки
// Подрешетка в горе
// формируем или нет

using System;

  

class GFG

{

      

    // Служебный метод для построения

    // левый и правый массив

    static void preprocess(int []arr, int N, 

                           int []left, int []right)

    {

        // инициализируем первый левый

        // индекс только как этот индекс

        left[0] = 0;

        int lastIncr = 0;

      

        for (int i = 1; i < N; i++)

        {

            // если текущее значение

            // больше, чем предыдущий,

            // обновляем последнее увеличение

            if (arr[i] > arr[i - 1])

                    lastIncr = i;

            left[i] = lastIncr;

        }

      

        // инициализируем последнее право

        // индекс только как этот индекс

        right[N - 1] = N - 1;

        int firstDecr = N - 1;

      

        for (int i = N - 2; i >= 0; i--)

        {

            // если текущее значение

            // больше следующего,

            // обновляем первый убывающий

            if (arr[i] > arr[i + 1])

                    firstDecr = i;

            right[i] = firstDecr;

        }

    }

      

    // метод возвращает true, если

    // arr [L..R] в горной форме

    static bool isSubarrayMountainForm(int []arr, int []left,

                                       int []right, int L, int R)

    {

        // возвращаем true только если верно

        // начальный диапазон больше

        // чем осталось в конце диапазона

        return (right[L] >= left[R]);

    }

      

      

    // Код драйвера

    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");

    }

}

  
// Этот код предоставлен aj_36


Выход:

Subarray is in mountain form
Subarray is not in mountain form

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найдите, находится ли подрешетка в форме горы или нет

0.00 (0%) 0 votes