រកមើលថាតើនាវាមុជទឹកស្ថិតក្នុងទម្រង់ជាភ្នំឬអត់


កម្រិតលំបាក រឹង
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon BlackRock ស៊ីស្កូ Citrix រោងចក្រ Honeywell ក្រុមហ៊ុន tesla Yandex
អារេ បញ្ហាសំណួរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ ស្វែងរកថាតើនាវាមុជទឹកស្ថិតក្នុងទម្រង់ជាភ្នំឬអត់” ចែងថាអ្នកត្រូវបានផ្តល់ឱ្យ integer អារេ និងជួរមួយ។ សេចក្តីថ្លែងការណ៍បញ្ហាសួរដើម្បីស្វែងយល់ថាតើអនុជួរដែលបង្កើតឡើងរវាងជួរដែលបានផ្តល់មានទំរង់ជាទម្រង់ភ្នំរឺអត់? ជួរភ្នំត្រូវបានបង្កើតឡើងប្រសិនបើលេខកំពុងកើនឡើងជាលំដាប់ឬក្នុងលំដាប់ថយចុះឬកើនឡើងដំបូងបន្ទាប់មកថយចុះ។

ឧទាហរណ៍

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

Left, right = (0, 3)
Mountain Form

ការពន្យល់

ដោយសារតែអនុជួរ {៣, ៤, ៥, ៦} កំពុងតែកើនឡើងដូច្នេះវាជាទម្រង់នៃជួរភ្នំ។

រកមើលថាតើនាវាមុជទឹកស្ថិតក្នុងទម្រង់ជាភ្នំឬអត់

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

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

ការពន្យល់

ដោយសារតែអារេរង {៥, ១, ២} កំពុងថយចុះបន្ទាប់មកកើនឡើង។ ដូច្នេះវាមិនមែនជាទម្រង់នៃជួរភ្នំទេ។

ក្បួនដោះស្រាយ

  1. បង្កើតអារេពីរ អារេអិល និង arrayR មានទំហំដូចគ្នានឹងប្រវែងនៃអារេដើម។
  2. ចាប់ផ្តើមធាតុដំបូងនៃ arrayL និងធាតុចុងក្រោយនៃ arrayR ។
  3. ប្រសិនបើធាតុអារេបច្ចុប្បន្នធំជាងធាតុមុន។
    1. ធ្វើបច្ចុប្បន្នភាព ការកើនឡើងលេខ ទៅលិបិក្រម។
    2. កំណត់តម្លៃកំពុងកើនឡើងលេខទៅអារេអិល។
  4. ឆ្លងកាត់អារេពីស្តាំទៅខាងឆ្វេងហើយពិនិត្យមើលថាតើលេខធំជាងធាតុមុន (ធាតុនៅខាងស្តាំនៃធាតុបច្ចុប្បន្ន) ។
    1. បន្ទាប់មកធ្វើឱ្យទាន់សម័យ ថយចុះនឹមប៊ឺរ ទៅលិបិក្រម
    2. ចាត់តាំងអារេអ័រដើម្បីបន្ថយន័រប៊ឺរ។
  5. សម្រាប់រាល់សំណួរដែលបានផ្តល់ឱ្យអារេR [ខាងឆ្វេង] ធំជាងអារេអិល [ខាងស្តាំ] ពិតហើយផ្សេងទៀតមិនពិតទេ។

ការពន្យល់

យើងបានផ្តល់អារេចំនួនគត់និងជួរខាងឆ្វេង, ស្តាំ។ យើងបានស្នើសុំឱ្យរកមើលថាតើនាវាមុជទឹកដែលបានបង្កើតឡើងជាមួយជួរដែលបានផ្តល់អាចជាជួរភ្នំឬអត់។ ប្រសិនបើនាវាមុជទឹកដែលបានបង្កើតឡើងគឺជាជួរភ្នំនោះយើងនឹងត្រលប់ជាការពិតបើមិនដូច្នេះទេវានឹងមិនពិត។ យើងនឹងប្រកាសអារេពីរ។ មួយគឺសម្រាប់ផ្នែកខាងឆ្វេងនៃអារេនិងមួយទៀតគឺសម្រាប់ផ្នែកខាងស្តាំនៃអារេ។ បន្ទាប់មកយើងនឹងសាងសង់អារេទាំងនេះដើម្បីឱ្យសំណួរនីមួយៗអាចផ្តល់នូវដំណោះស្រាយក្នុងចន្លោះថេរ។

យើងនឹងចាប់ផ្តើមធាតុដំបូងនិងធាតុចុងក្រោយនៃអារេដែលយើងបានបង្កើត arrayL និង arrayR រៀងៗខ្លួន។ បន្ទាប់មកយើងឆ្លងកាត់អារេសម្រាប់ផ្នែកខាងឆ្វេងនៃអារេឬយើងអាចនិយាយពីឆ្វេងទៅស្តាំ។ យើងនឹងពិនិត្យមើលលក្ខខណ្ឌប្រសិនបើធាតុអារេបច្ចុប្បន្នតិចជាងធាតុមុន។ ប្រសិនបើវាត្រូវបានគេរកឃើញថាជាការពិតនោះយើងនឹងធ្វើបច្ចុប្បន្នភាពការកើនឡើងទៅនឹងសន្ទស្សន៍នៃលេខ។ ហើយចាត់តាំងធាតុបច្ចុប្បន្នរបស់អារេអិលទៅអិនធឺរណែតដែលកំពុងកើនឡើងរាល់ពេលដោយមិនគោរពលក្ខខណ្ឌគឺពិតឬមិនពិត។

នៅជំហានបន្ទាប់យើងនឹងឆ្លងកាត់អារេពីស្តាំទៅឆ្វេងជាទូទៅពីធាតុចុងក្រោយទីពីរទៅធាតុទីមួយនៃអារេហើយពិនិត្យមើលថាតើធាតុបច្ចុប្បន្នរបស់អារេធំជាងធាតុបន្ទាប់។ ចាប់តាំងពីយើងកំពុងឆ្លងកាត់ពីឆ្វេងទៅស្តាំយើងអាចនិយាយថាពិនិត្យមើលជាមួយធាតុមុន។ ប្រសិនបើលក្ខខណ្ឌគឺត្រឹមត្រូវឬពិតនោះការថយចុះតម្លៃរបស់ផ្លាកផ្លឺត្រូវបានប្តូរទៅសន្ទស្សន៍បច្ចុប្បន្ន។ ធ្វើបច្ចុប្បន្នភាពអារេទៅនឹងការថយចុះន័របឺរដោយមិនគិតពីលក្ខខណ្ឌ។ ត្រឡប់ពិតប្រសិនបើជួរអារេ [ខាងឆ្វេង] ធំជាងឬស្មើអារេអិលខាងស្តាំបើមិនដូច្នោះទេនឹងត្រឡប់មិនពិត។

លេខកូដ

កូដ 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

កូដចាវ៉ាដើម្បីរកមើលថាតើនាវាមុជទឹកស្ថិតក្នុងទម្រង់ជាភ្នំឬអត់

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) សម្រាប់សាងសង់អារេទាំងពីរ។ ហើយនៅពេលដែលអារេត្រូវបានសាងសង់។ យើងអាចឆ្លើយសំណួរនៅក្នុងអូ (១) ។

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។