ຊອກຫາວ່າ subarray ແມ່ນຢູ່ໃນຮູບແບບຂອງພູເຂົາຫຼືບໍ່


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Amazon BlackRock Cisco Citrix ປັດໃຈ Honeywell Tesla Yandex
Array ບັນຫາການສອບຖາມ

ຖະແຫຼງການບັນຫາ

ບັນຫາ "ຊອກຫາວ່າ subarray ແມ່ນໃນຮູບແບບຂອງພູເຂົາຫຼືບໍ່" ລະບຸວ່າທ່ານໄດ້ຮັບການ integer array ແລະຊ່ວງ ໜຶ່ງ. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຂໍໃຫ້ຄົ້ນພົບວ່າແຖວຍ່ອຍທີ່ສ້າງຂື້ນລະຫວ່າງຂອບເຂດທີ່ ກຳ ນົດໄວ້ແມ່ນຮູບແບບພູເຂົາຫລືບໍ່? ຂບວນພູເຂົາຖືກສ້າງຕັ້ງຂື້ນຖ້າຫາກວ່າຕົວເລກຢູ່ໃນລະດັບທີ່ເພີ້ມຂື້ນຫຼືໃນລະດັບທີ່ຫຼຸດລົງຫລືເພີ່ມຂື້ນຄັ້ງ ທຳ ອິດຈາກນັ້ນກໍ່ຈະຫລຸດລົງ.

ຍົກຕົວຢ່າງ

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. ສ້າງສອງອາຄານ arrayL ແລະ arrayR ມີຂະ ໜາດ ເທົ່າກັບຄວາມຍາວຂອງຂບວນເດີມ.
  2. ເລີ່ມຕົ້ນອົງປະກອບ ທຳ ອິດຂອງ arrayL ແລະອົງປະກອບສຸດທ້າຍຂອງ arrayR.
  3. ຖ້າຫາກວ່າອົງປະກອບຂບວນໃນປະຈຸບັນສູງກວ່າອົງປະກອບທີ່ຜ່ານມາ.
    1. ປັບປຸງໃຫ້ທັນ ການເພີ່ມຂື້ນຂອງໄມ້ທ່ອນ ກັບດັດຊະນີ.
    2. ກໍາຫນົດມູນຄ່າເພີ່ມNumberໃຫ້ກັບ arrayL.
  4. ຂ້າມອາເລຈາກຂວາໄປທາງຊ້າຍແລະກວດເບິ່ງວ່າຕົວເລກໃຫຍ່ກວ່າອົງປະກອບທີ່ຜ່ານມາ (ອົງປະກອບທີ່ຢູ່ເບື້ອງຂວາຂອງປັດຈຸບັນ).
    1. ຫຼັງຈາກນັ້ນ, ປັບປຸງການ ລົດທີ່ຫລຸດລົງ ກັບດັດຊະນີ
    2. ກໍາຫນົດ arrayR ໃຫ້ຫຼຸດລົງ Number.
  5. ສຳ ລັບທຸກໆ ຄຳ ຖາມທີ່ໃຫ້ໄວ້, arrayR [ເບື້ອງຊ້າຍ] ແມ່ນໃຫຍ່ກວ່າການສົ່ງກັບຄືນຂອງ arrayL [right], ແມ່ນອີກບໍ່ຈິງ.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ມອບແຖວໂຕເລກແລະແຖວຊ້າຍ, ຂວາ. ພວກເຮົາໄດ້ຮ້ອງຂໍໃຫ້ຊອກຫາວ່າ subarray ທີ່ຖືກສ້າງຕັ້ງຂຶ້ນດ້ວຍຂອບເຂດທີ່ໄດ້ຮັບສາມາດເປັນແຖວພູຫຼືບໍ່. ຖ້າຫາກວ່າ subarray ສ້າງຕັ້ງຂຶ້ນດັ່ງນັ້ນແມ່ນຂບວນພູຫຼັງຈາກນັ້ນພວກເຮົາຈະກັບຄືນມາເປັນຄວາມຈິງ, ຖ້າບໍ່ດັ່ງນັ້ນຈະກັບຄືນບໍ່ຖືກຕ້ອງ. ພວກເຮົາຈະປະກາດສອງອາຄານ. ໜຶ່ງ ແມ່ນ ສຳ ລັບເບື້ອງຊ້າຍຂອງອາເລແລະອີກເບື້ອງ ໜຶ່ງ ແມ່ນ ສຳ ລັບເບື້ອງຂວາຂອງອາເລ. ຈາກນັ້ນພວກເຮົາຈະສ້າງອາຄານເຫຼົ່ານີ້ເພື່ອໃຫ້ການສອບຖາມແຕ່ລະຄົນສາມາດແກ້ໄຂບັນຫາໃນພື້ນທີ່ຄົງທີ່.

ພວກເຮົາຈະເລີ່ມຕົ້ນອົງປະກອບ ທຳ ອິດແລະສຸດທ້າຍຂອງອາເລທີ່ພວກເຮົາສ້າງ arrayL ແລະ arrayR ຕາມ ລຳ ດັບ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາຂ້າມອາຄານ ສຳ ລັບເບື້ອງຊ້າຍຂອງອາເລຫລືພວກເຮົາສາມາດເວົ້າຈາກຊ້າຍຫາຂວາ. ພວກເຮົາຈະກວດສອບສະພາບການຖ້າວ່າປັດໃຈ array ໃນປະຈຸບັນແມ່ນ ໜ້ອຍ ກວ່າອົງປະກອບທີ່ຜ່ານມາ ຖ້າມັນພົບວ່າມັນເປັນຄວາມຈິງ, ແລ້ວພວກເຮົາຈະປັບປຸງເລກທີ່ເພີ່ມຂື້ນຂື້ນມາສູ່ດັດຊະນີຂອງ ຈຳ ນວນ. ແລະຈັດແຈງອົງປະກອບປັດຈຸບັນຂອງ arrayL ໃຫ້ນັບມື້ນັບເພີ່ມຂື້ນທຸກໆຄັ້ງໂດຍບໍ່ສົນເລື່ອງຂອງເງື່ອນໄຂແມ່ນຄວາມຈິງຫຼືບໍ່.

ໃນຂັ້ນຕອນຕໍ່ໄປພວກເຮົາຈະ ກຳ ລັງລ້ຽວແຖວຈາກຂວາຫາຊ້າຍ, ໂດຍພື້ນຖານຈາກອົງປະກອບສຸດທ້າຍອັນດັບສອງໄປຫາອົງປະກອບ ທຳ ອິດຂອງອາເລ, ແລະກວດເບິ່ງວ່າປັດຈຸບັນຂອງ array ແມ່ນໃຫຍ່ກວ່າອົງປະກອບຕໍ່ໄປ. ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງຂ້າມຈາກຂວາຫາຊ້າຍ, ພວກເຮົາສາມາດເວົ້າວ່າກວດສອບກັບອົງປະກອບທີ່ຜ່ານມາ. ຖ້າສະພາບການແມ່ນຖືກຕ້ອງຫຼືຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນມູນຄ່າຫຼຸດລົງຂອງ ໝາກ ໄມ້ຖືກປ່ຽນໄປສູ່ດັດຊະນີປັດຈຸບັນ. ປັບປຸງແຖວໃຫ້ຖືກຫຼຸດລົງໂດຍບໍ່ ຄຳ ນຶງເຖິງເງື່ອນໄຂ. ກັບມາເປັນຄວາມຈິງ, ຖ້າ 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" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.