Знайдзіце, ці ёсць падмасіў у выглядзе горы ці не  


Узровень складанасці Жорсткі
Часта пытаюцца ў амазонка 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 значэнне, якое павялічваеццаНалічэнне.
  4. Перабярыце масіў справа налева і праверце, ці большая колькасць, чым папярэдні элемент (элемент справа ад бягучага элемента).
    1. Затым абнавіць памяншаеццаКолькасць да індэкса
    2. Прызначыць масіўR паменшальнамуКалі.
  5. Для кожнага дадзенага запыту arrayR [злева] больш, чым arrayL [справа] return true, інакш return false.
Глядзіце таксама
Двайковы масіў пасля аперацый пераключэння дыяпазону М

Тлумачэнне  

Мы прывялі цэлы масіў і дыяпазон злева, справа. Мы папрасілі высветліць, ці можа падмасіў, утвораны такім чынам з дадзеным дыяпазонам, быць горным масівам. Калі падмасіў, які ўтварыўся такім чынам, з'яўляецца масівам гор, мы вернем ісціну, інакш вернем ілжыва. Мы аб'явім два масівы. Адзін прызначаны для левага боку масіва, а другі - для правага боку масіва. Тады мы будзем будаваць гэтыя масівы, каб кожны запыт мог даць рашэнне ў пастаяннай прасторы.

Мы ініцыялізуем першы і апошні элементы масіва, які мы стварылі arrayL і arrayR адпаведна. Затым мы праходзім па масіве з левага боку масіва альбо можам сказаць злева направа. Мы праверым умову, калі бягучы элемент масіва менш папярэдняга элемента. Калі гэта будзе прызнана праўдай, мы абнавім павялічваючы лік да індэкса ліку. І прысвойвайце бягучы элемент arrayL 'нарастаючайNumber кожны раз, незалежна ад умовы, праўда ці не.

На наступным этапе мы пройдзем масіў справа налева, у асноўным ад другога апошняга элемента да першага элемента масіва, і праверым, ці больш бягучы элемент масіва, чым наступны элемент. Паколькі мы рухаемся справа налева, мы можам сказаць праверыць з папярэднім элементам. Калі ўмова правільная ці праўдзівая, значэнне decreasingNumber змяняецца на бягучы індэкс. Абнавіце масіў на памяншальны нумар незалежна ад умоў. Вяртае true, калі масіўR [злева] больш альбо роўны масівуL [справа], у адваротным выпадку вяртаецца false.

Глядзіце таксама
Паліндром звязаны спіс Leetcode рашэнне

код  

Код 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).

Глядзіце таксама
Рашэнне з міні-стэкам Leetcode

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве.