Намерете дали подмасивът е под формата на планина или не  


Ниво на трудност Трудно
Често задавани в Амазонка BlackRock Cisco Citrix FactSet Honeywell Tesla Yandex
Array Задача за заявка

Декларация за проблема  

Проблемът „Намерете дали подмасивът е под формата на планина или не“ гласи, че сте получили цяло число масив и диапазон. Изложението на проблема иска да разбере дали подмасивът, образуван между дадения диапазон, е под формата на планинска форма или не? Планински масив се формира, ако номерата са в нарастващ ред или в намаляващ ред или първо се увеличава, а след това намалява.

Пример  

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. Инициализирайте първия елемент на arrayL и последния елемент на arrayR.
  3. Ако текущият елемент на масива е по-голям от предишния елемент.
    1. Актуализирайте увеличаващБрой към индекса.
    2. Присвоете стойността нарастващоНимер на масиваL.
  4. Преместете масива отдясно наляво и проверете дали числото е по-голямо от предишния елемент (елементът отдясно на текущия елемент).
    1. След това обновете намаляващБрой към индекса
    2. Присвояване на arrayR на намаляващNumber.
  5. За всяка дадена заявка arrayR [ляво] е по-голямо от arrayL [дясно] връща true, в противен случай връща false.
Вижте също
Двоичен масив след операции за превключване на М диапазон

Обяснение  

Дадохме цял масив и диапазон вляво, вдясно. Поискахме да разберем дали така образуваният подмасив с дадения обхват може да бъде планински масив или не. Ако така образуваният подмасив е планински масив, тогава ние ще върнем true, в противен случай връщаме false. Ще декларираме два масива. Единият е за лявата страна на масива, а другият е за дясната страна на масива. Тогава ще изградим тези масиви, така че всяка заявка да може да даде решение в постоянно пространство.

Ще инициализираме първия и последния елемент от масива, който създадохме съответно arrayL и arrayR. След това прекосяваме масива за лявата страна на масива или можем да кажем отляво надясно. Ще проверим условието дали текущият елемент на масива е по-малък от предишния елемент. Ако се установи, че е вярно, тогава ще актуализираме нарастващото число до индекса на числото. И присвоявайте текущия елемент на arrayL 'на нарастващияNumber всеки път, независимо дали условието е вярно или не.

В следващата стъпка ще преминем през масива отдясно наляво, основно от втория последен елемент към първия елемент на масива и ще проверим дали текущият елемент на масива е по-голям от следващия елемент. Тъй като се движим отдясно наляво, можем да кажем чек с предишния елемент. Ако условието е вярно или вярно, тогава намаляващата стойност се променя на текущия индекс. Актуализирайте масива до намаляващото число, независимо от условията. Връща true, ако arrayR [ляво] е по-голямо или равно на масиваL [дясно], иначе връща false.

Вижте също
Решение за Leetcode на Linindrome Linked List

код  

C ++ код, за да открие дали подмасивът е под формата на планина или не

#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).

Вижте също
Min Stack Leetcode решение

Сложност на пространството

О (п) където "н" е броят на елементите в масива.