Monotonic Array LeetCode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ເຟສບຸກ
Array

ບັນຫາບັນຫາ

ໃນບັນຫາ "Arot Monotonic" ພວກເຮົາໄດ້ຮັບການຈັດແຈງ. ໜ້າ ວຽກຂອງພວກເຮົາແມ່ນກວດສອບວ່າອາເລແມ່ນບໍ monotonic ຂອດຫລືບໍ່.

ຂບວນ monotonic ແມ່ນອາເລທີ່ບັນດາອົງປະກອບຕ່າງໆຖືກຈັດຮຽງຕາມ ລຳ ດັບທີ່ເພີ່ມຂື້ນຫຼືຫຼຸດລົງຕາມ ລຳ ດັບ. ຖ້າອາເລຖືກຈັດຮຽງຕາມ ລຳ ດັບທີ່ເພີ່ມຂື້ນຫຼັງຈາກນັ້ນ ສຳ ລັບ array ທີ່ເຂົ້າມາ [], ມາຮອດ [i] <= arr [i + 1]. ສຳ ລັບແຖວທີ່ຖືກຈັດຮຽງຕາມ ລຳ ດັບຫຼຸດລົງ, ມາຮອດ [i]> = ມາຮອດ [i + 1].

ຫນ້າທີ່ຄວນຈະກັບຄືນມາເປັນຄວາມຈິງໃນເວລາທີ່ຂບວນແມ່ນ monotonic. ຖ້າບໍ່ດັ່ງນັ້ນ, ກັບຄືນບໍ່ຖືກຕ້ອງ.

ຍົກຕົວຢ່າງ

arr={1,2,4,5}
true

ຄໍາອະທິບາຍ:  ໃນແຖວທີ່ວາງໄວ້ ສຳ ລັບແຕ່ລະຂ້ອຍມາຮອດ [ຂ້ອຍ]

ວິທີການ

ເພື່ອແກ້ໄຂບັນຫານີ້ມັນເປັນສິ່ງ ສຳ ຄັນທີ່ສຸດທີ່ຈະຕ້ອງເຂົ້າໃຈຢ່າງຈະແຈ້ງວ່າແມ່ນຂອດ monotonic.

ຂບວນ monotonic ແມ່ນຂບວນການ ໜຶ່ງ ທີ່ຖ້າພວກເຮົາ ກຳ ນົດເສັ້ນສະແດງລະຫວ່າງ ຈຳ ນວນດັດສະນີແລະມູນຄ່າທີ່ດັດຊະນີຂອງ array ນັ້ນມັນກໍ່ຈະເປັນເສັ້ນສະແດງ monotonic ທີ່ເພີ່ມຂຶ້ນຫລືຫຼຸດລົງ. ຮູບພາບຂ້າງລຸ່ມນີ້ສະແດງເສັ້ນສະແດງ monotonic ທີ່ເພີ່ມຂື້ນແລະຫຼຸດລົງ.

ການແກ້ໄຂ leetcode ກັບ Monotonic Array

ວິທີການໃນການແກ້ໄຂບັນຫານີ້ແມ່ນຄ້າຍຄື, ພວກເຮົາຈະລວບລວມອາເລແລະກວດເບິ່ງວ່າມັນເປັນຂບວນທີ່ເພີ່ມຂື້ນໂດຍການກວດສອບ arr [i] <= arr [i + 1]. ຖ້າວ່າມັນເປັນອາເລທີ່ເພີ່ມຂື້ນແລ້ວອາເລທີ່ໃຫ້ແມ່ນ alotonic ອີກອັນ ໜຶ່ງ ພວກເຮົາຈະຂ້າມ array ໄປອີກຄັ້ງແລະກວດເບິ່ງວ່າມັນເປັນ array ທີ່ຫລຸດລົງໂດຍກວດເບິ່ງວ່າ arr [i]> = arr [i + 1] ຖ້າຫາກວ່າມັນເປັນອາເລທີ່ຫລຸດລົງ, ອາເລທີ່ມອບໃຫ້ແມ່ນຂບວນໂມໂນໂມນອີກອັນ ໜຶ່ງ ມັນບໍ່ແມ່ນຂບວນ monotonic.

ພວກເຮົາຍັງສາມາດກວດເບິ່ງວ່າອາເລເພີ່ມຂື້ນຫລືຫຼຸດລົງໂດຍໃຊ້ພຽງເສັ້ນທາງດຽວ. ພວກເຮົາຈະໃຊ້ສອງ isincr ແລະ isdec ແລະເລີ່ມຕົ້ນດ້ວຍຄວາມຈິງ. ຖ້າ A [i]> A [i + 1] ຫຼັງຈາກນັ້ນ isincr ຈະກາຍເປັນສິ່ງທີ່ບໍ່ຖືກຕ້ອງແລະຖ້າ A [i] <A [i + 1] ຫຼັງຈາກນັ້ນ isdec ກໍ່ຈະກາຍເປັນຄວາມຈິງ. ຖ້າຫາກວ່າອາເລແມ່ນ monotonic ຫຼັງຈາກນັ້ນຢ່າງຫນ້ອຍຫນຶ່ງຂອງ isincr ແລະ isdec ຈະເປັນຄວາມຈິງ. ເມື່ອທັງສອງບໍ່ຖືກຕ້ອງ ໝາຍ ຄວາມວ່າອາເລບໍ່ແມ່ນ monotonic ເພາະຄ່າທັງສອງທີ່ບໍ່ຖືກຕ້ອງຊີ້ໃຫ້ເຫັນວ່າຄ່າໃນ array ແມ່ນທັງເພີ່ມຂຶ້ນແລະຫຼຸດລົງ.

 

ລະຫັດ

C ++ Monotonic Array LeetCode Solution

#include <bits/stdc++.h> 
using namespace std; 
        bool isMonotonic(vector<int>& A) {
        bool isincr = true;
        bool isdec = true;
        int n=A.size();
        for (int i = 0; i < n- 1; ++i) {
            if (A[i] > A[i+1])
                isincr = false;
            if (A[i] < A[i+1])
               isdec = false;
        }

        return isincr || isdec;   
    }

int main() 
{ 
 vector<int> arr = {1,2,4,5}; 
 cout <<boolalpha;
 cout<<isMonotonic(arr)<<endl; 
 return 0;
}
true

Java Monotonic Array LeetCode Solution

import java.util.Arrays; 
public class Tutorialcup {
    public  static  boolean isMonotonic(int[] A) {
        boolean isincr = true;
        boolean isdec = true;
        int n=A.length;
        for (int i = 0; i < n- 1; ++i) {
            if (A[i] > A[i+1])
                isincr = false;
            if (A[i] < A[i+1])
               isdec = false;
        }

        return isincr || isdec;   
}
  public static void main(String[] args) {
    int [] arr = {1,2,4,5}; 
    boolean ans= isMonotonic(arr);
    System.out.println(ans);
  }
}
true

ການວິເຄາະຄວາມສັບສົນຂອງ Monotonic Array

ຄວາມສັບສົນເວລາ

ຄວາມສັບສົນຂອງເວລາຂອງລະຫັດຂ້າງເທິງແມ່ນ O (n) ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງກວດກາອາເລພຽງຄັ້ງດຽວເພື່ອກວດກາເບິ່ງວ່າມັນແມ່ນຂອດ monotonic ຫຼືບໍ່. ນີ້ n ແມ່ນຂະ ໜາດ ຂອງຂບວນການປ້ອນຂໍ້ມູນ.

ຄວາມສັບສົນໃນອະວະກາດ

ຄວາມສັບສົນໃນພື້ນທີ່ຂອງລະຫັດຂ້າງເທິງແມ່ນ O (1) ເພາະວ່າພວກເຮົາ ກຳ ລັງໃຊ້ຕົວແປເທົ່ານັ້ນເພື່ອເກັບ ຄຳ ຕອບ.

ເອກະສານ