Bilangan Minimum Penyingkiran untuk Membuat Mountain Array

1671. Bilangan Minimum Penyingkiran untuk Membuat Mountain Array

Kesukaran: Sukar

Topik: Tatasusunan, Carian Binari, Pengaturcaraan Dinamik, Tamak

Anda mungkin ingat bahawa susunan tatasusunan ialah tatasusunan gunung jika dan hanya jika:

• arr.length >= 3
• Terdapat beberapa indeks i (0-diindeks) dengan 0 < i < arr.length - 1 supaya:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i 1] > ... > arr[arr.length - 1]

  Memandangkan nombor tatasusunan integer, kembalikan bilangan minimum elemen untuk dialih keluar untuk menjadikan nombor sebagai tatasusunan gunung.

  Contoh 1:

  • Input: nombor = [1,3,1]
  • Output: 0
  • Penjelasan: Tatasusunan itu sendiri ialah tatasusunan gunung jadi kita tidak perlu mengalih keluar sebarang unsur.

  Contoh 2:

  • Input: nombor = [2,1,1,5,6,2,3,1]
  • Output: 3
  • Penjelasan: Satu penyelesaian ialah mengalih keluar elemen pada indeks 0, 1, dan 5, menjadikan nombor tatasusunan = [1,5,6,3,1].

  Kekangan:

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 10⁹
  • Dijamin anda boleh membuat susunan gunung daripada nombor.

  Petunjuk:

  1. Fikirkan arah yang bertentangan dan bukannya elemen minimum untuk mengalih keluar urutan gunung maksimum
  2. Fikirkan LIS ni macam dekat je

  Penyelesaian:

  Kita boleh menggunakan pendekatan pengaturcaraan dinamik dengan idea mencari urutan gunung maksimum dan bukannya mengira terus elemen untuk dialih keluar. Pendekatan ini adalah berdasarkan kepada mencari dua Turutan Meningkat Terpanjang (LIS) untuk setiap kedudukan dalam tatasusunan: satu pergi kiri-ke-kanan dan satu lagi pergi kanan-ke- kiri. Sebaik sahaja kita mempunyai jujukan gunung yang paling lama mungkin, perbezaan antara panjang tatasusunan asal dan panjang jujukan ini akan memberi kita elemen minimum untuk dialih keluar.

  Rangka Penyelesaian

  1. Kenal pasti panjang jujukan yang semakin meningkat:

     • Kira tatasusunan leftLIS, dengan leftLIS[i] mewakili panjang jujukan peningkatan terpanjang yang berakhir pada i (menuju kiri ke kanan).

  2. Kenal pasti panjang jujukan yang semakin berkurang:

     • Kira tatasusunan rightLIS, dengan rightLIS[i] mewakili panjang urutan menurun terpanjang bermula pada i (menuju kanan ke kiri).

  3. Kira panjang gunung maksimum:

     • Untuk setiap indeks i dengan 0 < i < n - 1, semak sama ada terdapat puncak yang sah (iaitu, kiriLIS[i] > 1 dan kananLIS[i] > 1). Kira panjang gunung di i sebagai kiriLIS[i] kananLIS[i] - 1.

  4. Dapatkan penyingkiran minimum:

     • Elemen minimum untuk dialih keluar ialah panjang tatasusunan asal tolak panjang gunung terpanjang ditemui.

  Mari kita laksanakan penyelesaian ini dalam PHP: 1671. Bilangan Minimum Penyingkiran untuk Membuat Mountain Array
  

  <?php
  /**
   * @param Integer[] $nums
   * @return Integer
   */
  function minimumMountainRemovals($nums) {
      ...
      ...
      ...
      /**
       * go to ./solution.php
       */
  }
  
  // Example usage
  $nums1 = [1, 3, 1];
  echo minimumMountainRemovals($nums1); // Output: 0
  
  $nums2 = [2, 1, 1, 5, 6, 2, 3, 1];
  echo minimumMountainRemovals($nums2); // Output: 3
  ?>
  

  Penjelasan:

  1. Pengiraan LIS Kiri:

     • leftLIS[i] menyimpan panjang maksimum bagi urutan yang semakin meningkat berakhir pada i. Kami mengulangi setiap i, dan untuk setiap i, mengulangi dari 0 hingga i-1 untuk mencari urutan terpanjang yang berakhir pada i.

  2. Pengiraan LIS Kanan:

     • rightLIS[i] menyimpan panjang maksimum bagi urutan yang semakin berkurangan bermula pada i. Kami mengundur ke belakang daripada n-2 kepada 0, dan untuk setiap i, mengulangi daripada n-1 ke i 1 untuk mencari jujukan terpanjang bermula pada i.

  3. Pengiraan Gunung:

     • Puncak yang sah pada indeks i mesti meninggalkanLIS[i] > 1 dan kananLIS[i] > 1. Panjang gunung dengan puncak di i ialah kiriLIS[i] kananLIS[i] - 1.

  4. Pengiraan Akhir:

     • Penyingkiran minimum yang diperlukan ialah perbezaan antara panjang tatasusunan asal dan panjang gunung maksimum yang ditemui.

  Analisis Kerumitan

  • Kerumitan Masa: O(n²), disebabkan oleh gelung berganda dalam pengiraan LIS.
  • Kerumitan Angkasa: O(n), untuk menyimpan tatasusunan LIS kiri dan kanan.

  Penyelesaian ini memastikan bahawa kami mencari jujukan gunung maksimum dan mengira penyingkiran minimum yang diperlukan untuk mencapai susunan gunung.

  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 Bilangan Minimum Penyingkiran untuk Membuat Mountain Array. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!