ค้นหาว่า subarray อยู่ในรูปของภูเขาหรือไม่


ระดับความยาก ยาก
ถามบ่อยใน อเมซอน แบล็ค ซิสโก้ ซิทริกซ์ ข้อเท็จจริง Honeywell เทสลา Yandex
แถว ปัญหาการสืบค้น

คำชี้แจงปัญหา

ปัญหา“ ค้นหาว่า subarray อยู่ในรูปของภูเขาหรือไม่” ระบุว่าคุณได้รับไฟล์ จำนวนเต็ม แถว และช่วง คำสั่งปัญหาถามเพื่อค้นหาว่าอาร์เรย์ย่อยที่เกิดขึ้นระหว่างช่วงที่กำหนดนั้นอยู่ในรูปแบบของภูเขาหรือไม่? เมาน์เทนอาร์เรย์เกิดขึ้นหากตัวเลขอยู่ในลำดับที่เพิ่มขึ้นหรือในลำดับที่ลดลงหรือเพิ่มขึ้นก่อนแล้วจึงลดลง

ตัวอย่าง

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

Left, right = (0, 3)
Mountain Form

คำอธิบาย

เนื่องจากอาร์เรย์ย่อย {3, 4, 5, 6} เพิ่มขึ้นดังนั้นจึงอยู่ในรูปแบบของอาร์เรย์ภูเขา

ค้นหาว่า subarray อยู่ในรูปของภูเขาหรือไม่

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

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

คำอธิบาย

เนื่องจากอาร์เรย์ย่อย {5, 1, 2} ลดลงจากนั้นจึงเพิ่มขึ้น ดังนั้นจึงไม่อยู่ในรูปแบบของอาร์เรย์ภูเขา

ขั้นตอนวิธี

  1. สร้างสองอาร์เรย์ อาร์เรย์ และ อาร์เรย์ มีขนาดเท่ากับความยาวของอาร์เรย์เดิม
  2. เริ่มต้นองค์ประกอบแรกของ arrayL และองค์ประกอบสุดท้ายของ arrayR
  3. หากองค์ประกอบอาร์เรย์ปัจจุบันมีค่ามากกว่าองค์ประกอบก่อนหน้า
    1. อัปเดต จำนวนที่เพิ่มขึ้น ไปที่ดัชนี
    2. กำหนดค่า IncreNumber ให้กับ arrayL
  4. สำรวจอาร์เรย์จากทางขวาไปทางซ้ายและตรวจสอบว่ามีจำนวนมากกว่าองค์ประกอบก่อนหน้าหรือไม่ (องค์ประกอบทางด้านขวาขององค์ประกอบปัจจุบัน)
    1. จากนั้นอัปเดต จำนวนที่ลดลง ไปที่ดัชนี
    2. กำหนด arrayR เพื่อลดจำนวน
  5. สำหรับทุกการค้นหา arrayR [ซ้าย] จะมากกว่า arrayL [ขวา] ส่งคืนจริงมิฉะนั้นจะส่งคืนเท็จ

คำอธิบาย

เราได้กำหนดอาร์เรย์จำนวนเต็มและช่วงซ้ายขวา เราได้ถามเพื่อดูว่า subarray ที่สร้างขึ้นในช่วงที่กำหนดสามารถเป็นอาร์เรย์ภูเขาได้หรือไม่ หาก subarray ที่เกิดขึ้นนั้นเป็นภูเขาอาร์เรย์เราจะคืนค่าจริงมิฉะนั้นจะคืนค่าเท็จ เราจะประกาศสองอาร์เรย์ อันหนึ่งใช้สำหรับด้านซ้ายของอาร์เรย์และอีกอันใช้สำหรับด้านขวาของอาร์เรย์ จากนั้นเราจะสร้างอาร์เรย์เหล่านี้เพื่อให้แต่ละแบบสอบถามสามารถให้คำตอบในพื้นที่คงที่

เราจะเริ่มต้นองค์ประกอบแรกและองค์ประกอบสุดท้ายของอาร์เรย์ที่เราสร้าง arrayL และ arrayR ตามลำดับ จากนั้นเราสำรวจอาร์เรย์สำหรับด้านซ้ายของอาร์เรย์หรือเราสามารถพูดจากซ้ายไปขวา เราจะตรวจสอบเงื่อนไขว่าองค์ประกอบอาร์เรย์ปัจจุบันน้อยกว่าองค์ประกอบก่อนหน้าหรือไม่ หากพบว่าเป็นจริงเราจะอัปเดตหมายเลขที่เพิ่มขึ้นเป็นดัชนีของตัวเลข และกำหนดองค์ประกอบปัจจุบันของ arrayL ให้กับ IncreNumber ทุกครั้งโดยไม่คำนึงถึงเงื่อนไขว่าเป็นจริงหรือไม่

ในขั้นตอนต่อไปเราจะข้ามอาร์เรย์จากขวาไปซ้ายโดยพื้นฐานจากองค์ประกอบสุดท้ายที่สองไปยังองค์ประกอบแรกของอาร์เรย์และตรวจสอบว่าองค์ประกอบปัจจุบันของอาร์เรย์มีค่ามากกว่าองค์ประกอบถัดไปหรือไม่ เนื่องจากเรากำลังลัดเลาะจากขวาไปซ้ายเราจึงพูดได้ว่าตรวจสอบกับองค์ประกอบก่อนหน้า ถ้าเงื่อนไขถูกต้องหรือเป็นจริงค่าที่ลดลงจะเปลี่ยนเป็นดัชนีปัจจุบัน อัปเดตอาร์เรย์เป็นจำนวนที่ลดลงโดยไม่คำนึงถึงเงื่อนไข ส่งกลับจริงถ้า arrayR [ซ้าย] มากกว่าหรือเท่ากับ arrayL [ขวา] มิฉะนั้นจะส่งคืนเท็จ

รหัส

รหัส C ++ เพื่อค้นหาว่า subarray อยู่ในรูปของภูเขาหรือไม่

#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 เพื่อค้นหาว่า subarray อยู่ในรูปของภูเขาหรือไม่

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)

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์