Գտեք ՝ ենթաշերտը լեռան տեսքով է, թե ոչ


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Amazon Blackrock Cisco Citrix Փաստեր HONEYWELL Tesla Yandex
Դասավորություն Հարցման խնդիր

Խնդիրի հայտարարություն

«Գտեք ՝ ենթաշերտը լեռան տեսքով է, թե ոչ» խնդիրը ասում է, որ ձեզ տրված է ամբողջ թիվ դասավորություն և մի շարք: Խնդրի դրույթը խնդրում է պարզել, թե տվյալ տիրույթի միջև գոյացած ենթաշարայնը լեռնային տեսքով է, թե ոչ: Լեռնային զանգվածը ձեւավորվում է, եթե թվերը աճող կարգով կամ նվազման կարգով են կամ առաջին հերթին աճում են, ապա նվազում:

Օրինակ

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. Ստեղծեք երկու զանգված զանգված և զանգված R նույն չափի, ինչ որ սկզբնական զանգվածի երկարությունը:
  2. Նախաձեռնեք զանգվածի առաջին տարրը և զանգվածի վերջին տարրը:
  3. Եթե ​​ընթացիկ զանգվածի տարրը ավելի մեծ է, քան նախորդ տարրը:
    1. Թարմացրեք աճող թիվ ինդեքսին:
    2. Արժեքը մեծացնող թիվը վերագրեք զանգվածին L:
  4. Անցեք զանգվածը աջից ձախ և ստուգեք արդյո՞ք նախորդից ավելի մեծ թիվ (ընթացիկ տարրի աջ կողմում գտնվող տարրը):
    1. Այնուհետեւ թարմացրեք նվազում է Թիվը ինդեքսին
    2. Arանգվածը վերագրեք նվազող թվին:
  5. Յուրաքանչյուր տրված հարցման համար arrayR- ը [ձախ] ավելի մեծ է, քան arrayL- ի [աջ] վերադարձը true, այլապես վերադարձը false:

բացատրություն

Մենք տվել ենք ամբողջ զանգված և ձախ, աջ տիրույթ: Մենք խնդրել ենք պարզել, արդյոք տրված տիրույթով այդքան կազմված ենթաշերտը կարող է լինել լեռնային զանգված, թե ոչ: Եթե ​​այդքան կազմված ենթաշերտը լեռնաշղթա է, մենք կվերադառնանք ճշմարիտ, հակառակ դեպքում կվերադառնանք կեղծ: Մենք հայտարարելու ենք երկու զանգված: Մեկը զանգվածի ձախ կողմի համար է, իսկ մյուսը `զանգվածի աջ կողմի: Դրանից հետո մենք կկառուցենք այս զանգվածները, որպեսզի յուրաքանչյուր հարցում կարողանա լուծում տալ կայուն տարածության մեջ:

Նախաձեռնարկելու ենք համապատասխանաբար arrayL և arrayR ստեղծած զանգվածի առաջին և վերջին տարրերը: Դրանից հետո մենք զանգվածը հատում ենք զանգվածի ձախ կողմի համար կամ կարող ենք ասել ՝ ձախից աջ: Մենք կստուգենք պայմանը, եթե ընթացիկ զանգվածի տարրը պակաս է նախորդ տարրից: Եթե ​​պարզվի, որ դա ճիշտ է, ապա մենք կավելացնենք աճող թիվը համարի ինդեքսին: Եվ ամեն անգամ աճող թվին հանձնարարիր զանգվածի ընթացիկ տարրը ՝ անկախ պայմանից ճիշտ է, թե ոչ:

Հաջորդ քայլում մենք կկողմնորոշենք զանգվածը աջից ձախ, հիմնականում երկրորդ վերջին տարրից մինչ զանգվածի առաջին տարրը և ստուգենք, արդյոք զանգվածի ընթացիկ տարրը ավելի մեծ է, քան հաջորդ տարրը: Քանի որ մենք անցնում ենք աջից ձախ, մենք կարող ենք ասել, որ ստուգեք նախորդ տարրով: Եթե ​​պայմանը ճիշտ է կամ ճիշտ է, ապա նվազող թվով արժեքը փոխվում է ընթացիկ ցուցանիշի: Updանգվածը թարմացրեք նվազող թվով `անկախ պայմաններից: Վերադարձիր ճշմարիտ, եթե զանգվածը R [ձախ] ավելի մեծ է կամ հավասար է զանգվածի [աջ], այլապես վերադարձիր false:

Կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N + Q), մեզ համար պահանջվում է O (N) ժամանակ և՛ զանգվածները կառուցելու համար: Եվ երբ զանգվածները կառուցվեն: Մենք կարող ենք պատասխանել O (1) հարցումներում:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: