Знайдіть, чи є підмасив формою гори чи ні


Рівень складності Жорсткий
Часто запитують у Амазонка BlackRock Cisco Citrix Факти Honeywell Тесла Яндекс
масив Проблема запиту

Постановка проблеми

Проблема "Знайти, чи є підмасив у формі гори чи ні", говорить про те, що вам дали ціле масив і діапазон. Постановка задачі вимагає з’ясувати, чи є підмасив, утворений між даним хребтом, у формі гірської форми чи ні? Гірський масив утворюється, якщо чисельність зростає або зменшується, або спочатку збільшується, а потім зменшується.

Приклад

arr[]={3,4,5,6,1,5,1,2,1}

Left, right = (0, 3)
Mountain Form

Пояснення

Оскільки підмасив {3, 4, 5, 6} збільшується, тож він має форму гірського масиву.

Знайдіть, чи є підмасив формою гори чи ні

arr[]={3,4,5,6,1,5,1,2,1}

Left, right = (5, 7)
Not a Mountain form

Пояснення

Оскільки підмасив {5, 1, 2} зменшується, а потім збільшується. Тож це не у вигляді гірського масиву.

Алгоритм

  1. Створіть два масиви масивL і масивR такого ж розміру, що і довжина оригінального масиву.
  2. Ініціалізуйте перший елемент масивуL та останній елемент масивуR.
  3. Якщо поточний елемент масиву більше попереднього елемента.
    1. Оновити збільшенняКількість до індексу.
    2. Присвоїти масивуL значенняNumber.
  4. Перемістіть масив справа наліво і перевірте, чи число більше за попередній елемент (елемент праворуч від поточного елемента).
    1. Потім оновіть зменшуєтьсяКількість до індексу
    2. Призначити arrayR до зменшуваногоNumber.
  5. Для кожного заданого запиту arrayR [зліва] перевищує масивL [справа] return true, інакше повертає false.

Пояснення

Ми дали цілочисельний масив і діапазон ліворуч, праворуч. Ми попросили з’ясувати, чи може такий масив, сформований із заданим ареалом, бути гірським масивом чи ні. Якщо так сформований підмасив є гірським масивом, тоді ми повернемо true, інакше повернемо false. Ми оголосимо два масиви. Один призначений для лівої сторони масиву, а інший - для правої сторони масиву. Тоді ми будемо будувати ці масиви, щоб кожен запит міг дати рішення у постійному просторі.

Ми ініціалізуємо перший та останній елементи масиву, який ми створили arrayL та arrayR відповідно. Потім ми обводимо масив ліворуч від масиву або можемо сказати зліва направо. Ми перевіримо умову, якщо поточний елемент масиву менше попереднього елемента. Якщо виявиться, що це істина, ми оновимо збільшенняNumber до індексу числа. І присвоюйте поточний елемент arrayL 'збільшувальномуNumber щоразу, незалежно від того, чи є умова істинним чи ні.

На наступному кроці ми здійснимо обхід масиву справа наліво, в основному від другого останнього елемента до першого елемента масиву, і перевіримо, чи поточний елемент масиву перевищує наступний елемент. Оскільки ми рухаємося справа наліво, ми можемо сказати перевірити за допомогою попереднього елемента. Якщо умова правильна або істинна, тоді значення decreasingNumber змінюється на поточний індекс. Оновіть масив до зменшуваного числа незалежно від умов. Повертає true, якщо масивR [зліва] більше або дорівнює масивуL [праворуч], інакше повертає false.

код

Код С ++, щоб визначити, чи є підмасив у формі гори чи ні

#include<iostream>

using namespace std;

void buildArrays(int arr[], int N, int arrayL[], int arrayR[])
{
    arrayL[0] = 0;
    int increasingNumber = 0;

    for (int i = 1; i < N; i++)
    {
        if (arr[i] > arr[i - 1])
            increasingNumber = i;
        arrayL[i] = increasingNumber;
    }
    arrayR[N - 1] = N - 1;
    int decreasingNumber = N - 1;

    for (int i = N - 2; i >= 0; i--)
    {
        if (arr[i] > arr[i + 1])
            decreasingNumber = i;
        arrayR[i] = decreasingNumber;
    }
}

bool solveQuery(int arr[], int arrayL[], int arrayR[], int Left, int Right)
{
    return (arrayR[Left] >= arrayL[Right]);
}

int main()
{
    int arr[] = {3,4,5,6,1,5,1,2,1};
    int N = sizeof(arr) / sizeof(int);

    int arrayL[N], arrayR[N];
    buildArrays(arr, N, arrayL, arrayR);

    int L = 0;
    int R = 3;
    if (solveQuery(arr, arrayL, arrayR, L, R))
        cout << "Mountain form\n";
    else
        cout << "Not a mountain form\n";

    L = 5;
    R = 7;
    if (solveQuery(arr, arrayL, arrayR, L, R))
        cout << "Mountain form\n";
    else
        cout << "Not a mountain form\n";

    return 0;
}
Mountain form
Not a mountain form

Код Java, щоб визначити, чи є підмасив у формі гори чи ні

class MountainArray
{
    static void buildArrays(int arr[], int N, int arrayL[], int arrayR[])
    {
        arrayL[0] = 0;
        int increasingNumber = 0;

        for (int i = 1; i < N; i++)
        {
            if (arr[i] > arr[i - 1])
                increasingNumber = i;
            arrayL[i] = increasingNumber;
        }
        arrayR[N - 1] = N - 1;
        int decreasingNumber = N - 1;

        for (int i = N - 2; i >= 0; i--)
        {
            if (arr[i] > arr[i + 1])
                decreasingNumber = i;
            arrayR[i] = decreasingNumber;
        }
    }
    
    static boolean solveQuery(int arr[], int arrayL[], int arrayR[], int Left, int Right)
    {
        return (arrayR[Left] >= arrayL[Right]);
    }

    public static void main(String[] args)
    {
        int arr[] = {3,4,5,6,1,5,1,2,1};
        int N = arr.length;
        int arrayL[] = new int[N];
        int arrayR[] = new int[N];
        buildArrays(arr, N, arrayL, arrayR);
        int L = 0;
        int R = 3;

        if (solveQuery(arr, arrayL, arrayR, L, R))
            System.out.println("Mountain form");
        else
            System.out.println("Not a mountain form");

        L = 5;
        R = 7;

        if (solveQuery(arr, arrayL, arrayR, L, R))
            System.out.println("Mountain form");
        else
            System.out.println("Not a mountain form");
    }
}
Mountain form
Not a mountain form

Аналіз складності

Складність часу

O (N + Q), нам потрібен час O (N) для побудови обох масивів. І як тільки масиви побудовані. Ми можемо відповісти на запитання в O (1).

Складність простору

О (п) де "N" - кількість елементів у масиві.