. Ketulan Max Untuk Diisih

769. Ketulan Maks Untuk Diisih

Kesukaran: Sederhana

Topik: Tatasusunan, Timbunan, Tamak, Isih, Timbunan Monotonic

Anda diberi arr tatasusunan integer dengan panjang n yang mewakili pilih atur integer dalam julat [0, n - 1].

Kami membahagikan arr kepada beberapa bilangan ketulan (iaitu, sekatan) dan mengisih setiap bahagian secara individu. Selepas menggabungkannya, hasilnya harus sama dengan tatasusunan yang diisih.

Kembalikan bilangan terbesar ketulan yang boleh kami buat untuk mengisih tatasusunan.

Contoh 1:

• Input: arr = [4,3,2,1,0]
• Output: 1
• Penjelasan:
  • Pecahan kepada dua atau lebih ketulan tidak akan mengembalikan hasil yang diperlukan.
  • Sebagai contoh, pemisahan kepada [4, 3], [2, 1, 0] akan menghasilkan [3, 4, 0, 1, 2], yang tidak diisih.

Contoh 2:

• Input: arr = [1,0,2,3,4]
• Output: 4
• Penjelasan:
  • Kita boleh berpecah kepada dua bahagian, seperti [1, 0], [2, 3, 4].
  • Walau bagaimanapun, pembahagian kepada [1, 0], [2], [3], [4] ialah bilangan ketulan tertinggi yang mungkin.

Kekangan:

• n == arr.panjang
• 1 <= n <= 10
• 0 <= arr[i] < n
• Semua elemen arr adalah unik.

Petunjuk:

1. Bongkah pertama boleh didapati sebagai k terkecil yang mana A[:k 1] == [0, 1, 2, ...k]; kemudian kita ulangi proses ini.

Penyelesaian:

Kita perlu mencari bilangan terbesar ketulan yang boleh dibentuk supaya setiap ketulan boleh diisih secara individu, dan apabila disatukan, hasilnya ialah versi disusun bagi keseluruhan tatasusunan.

Pendekatan:

1. Pemerhatian Utama:

   • Tatasusunan ialah pilih atur integer dari 0 hingga n-1. Ideanya adalah untuk melintasi tatasusunan dan mencari kedudukan di mana ketulan boleh dipisahkan.
   • Sesebuah bongkah boleh diisih jika, untuk semua indeks dalam bongkah, elemen maksimum sehingga titik itu tidak melebihi elemen minimum selepas titik itu dalam tatasusunan asal yang diisih.

2. Strategi:

   • Jejak nilai maksimum yang ditemui semasa anda melintasi dari kiri ke kanan.
   • Pada setiap indeks i, semak sama ada nilai maksimum sehingga i adalah kurang daripada atau sama dengan i. Jika syarat ini berlaku, ini bermakna anda boleh membahagi tatasusunan pada indeks tersebut kerana bahagian kiri boleh diisih secara berasingan.

3. Langkah:

   • Lelaran pada tatasusunan sambil mengekalkan maksimum berjalan.
   • Apabila maksimum larian menyamai indeks semasa, satu ketul boleh dibuat.
   • Kira bilangan ketulan tersebut.

Mari laksanakan penyelesaian ini dalam PHP: 769. Ketulan Maks Untuk Diisih

  
  
  Penjelasan:




Permulaan:


Kami bermula dengan maxSoFar = -1 untuk memastikan bahawa kami menjejaki nilai maksimum dalam tatasusunan dengan betul semasa kami melintasinya.

ketulan = 0 menjejaki bilangan ketulan yang boleh dibentuk.



Gelung:


Kami mengulangi setiap elemen dalam tatasusunan.
Untuk setiap elemen, kami mengemas kini maxSoFar menjadi nilai maksimum antara elemen semasa dan maksimum yang dilihat sebelum ini.
Jika maxSoFar == i, ini bermakna tatasusunan sehingga indeks i boleh diisih secara bebas dan ini adalah bahagian yang sah.
Kami menambah kiraan ketulan setiap kali keadaan ini berlaku.



Pulangan:


Akhir sekali, jumlah bilangan ketulan dikembalikan.





  
  
  Kerumitan Masa:




Kerumitan Masa: O(n), dengan n ialah panjang tatasusunan. Kami hanya membuat satu laluan melalui tatasusunan.

Kerumitan Angkasa: O(1), kerana kami hanya menggunakan beberapa pembolehubah untuk menyimpan hasil perantaraan.



  
  
  Contoh Panduan:


Untuk arr = [1, 0, 2, 3, 4]:


Pada indeks 0, nilai maksimum yang ditemui setakat ini ialah 1. Kami tidak boleh berpecah di sini.
Pada indeks 1, nilai maksimum ialah 1, yang sepadan dengan indeks semasa 1, jadi kita boleh berpecah kepada bahagian.
Pada indeks 2, nilai maksimum ialah 2, dan ia sepadan dengan indeks 2, jadi kami berpecah lagi.
Pada indeks 3, nilai maksimum ialah 3, dan ia sepadan dengan indeks 3, jadi kami berpecah lagi.
Pada indeks 4, nilai maksimum ialah 4 dan ia sepadan dengan indeks 4, jadi kami berpecah lagi.


Oleh itu, output untuk kes ini ialah 4 kerana kita boleh membahagikannya kepada 4 bahagian.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci . Ketulan Max Untuk Diisih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!