Cari Bangunan Tempat Alice dan Bob Boleh Bertemu

2940. Cari Bangunan Tempat Alice dan Bob Boleh Bertemu

Kesukaran: Sukar

Topik: Tatasusunan, Carian Perduaan, Tindanan, Pokok Berindeks Perduaan, Pokok Segmen, Timbunan (Baris Gilir Keutamaan), Timbunan Monotonic

Anda diberi ketinggian tatasusunan indeks 0 bagi integer positif, dengan ketinggian[i] mewakili ketinggian bangunan i^th.

Jika seseorang berada di dalam bangunan i, mereka boleh berpindah ke mana-mana bangunan lain j jika dan hanya jika i < j dan ketinggian[i] < ketinggian[j].

Anda juga diberi satu lagi pertanyaan tatasusunan di mana pertanyaan[i] = [a_i, b_i]. Pada pertanyaan i^th, Alice sedang membina_i manakala Bob sedang membina b_i.

Kembalikan tatasusunan dan dengan ans[i] ialah indeks bangunan paling kiri tempat Alice dan Bob boleh bertemu pada pertanyaan i^th. Jika Alice dan Bob tidak boleh berpindah ke bangunan biasa pada pertanyaan i, tetapkan ans[i] kepada -1.

Contoh 1:

• Input: ketinggian = [6,4,8,5,2,7], pertanyaan = [[0,1],[0,3],[2,4],[3,4] ,[2,2]]
• Output: [2,5,-1,5,2]
• Penjelasan: Dalam pertanyaan pertama, Alice dan Bob boleh beralih ke bangunan 2 sejak ketinggian[0] < ketinggian[2] dan ketinggian[1] < ketinggian[2].
  • Dalam pertanyaan kedua, Alice dan Bob boleh beralih ke bangunan 5 sejak ketinggian[0] < ketinggian[5] dan ketinggian[3] < ketinggian[5].
  • Dalam pertanyaan ketiga, Alice tidak dapat bertemu Bob kerana Alice tidak boleh berpindah ke mana-mana bangunan lain.
  • Dalam pertanyaan keempat, Alice dan Bob boleh beralih ke bangunan 5 sejak ketinggian[3] < ketinggian[5] dan ketinggian[4] < ketinggian[5].
  • Dalam pertanyaan kelima, Alice dan Bob sudah berada di bangunan yang sama.
  • Untuk ans[i] != -1, Ia boleh ditunjukkan bahawa ans[i] ialah bangunan paling kiri tempat Alice dan Bob boleh bertemu.
  • Untuk jawapan[i] == -1, Ia boleh ditunjukkan bahawa tiada bangunan di mana Alice dan Bob boleh bertemu.

Contoh 2:

• Input: ketinggian = [5,3,8,2,6,1,4,6], pertanyaan = [[0,7],[3,5],[5,2],[ 3,0],[1,6]]
• Output: [7,6,-1,4,6]
• Penjelasan: Dalam pertanyaan pertama, Alice boleh terus bergerak ke bangunan Bob sejak ketinggian[0] < ketinggian[7].
  • Dalam pertanyaan kedua, Alice dan Bob boleh beralih ke bangunan 6 sejak ketinggian[3] < ketinggian[6] dan ketinggian[5] < ketinggian[6].
  • Dalam pertanyaan ketiga, Alice tidak dapat bertemu Bob kerana Bob tidak boleh berpindah ke mana-mana bangunan lain.
  • Dalam pertanyaan keempat, Alice dan Bob boleh beralih ke bangunan 4 sejak ketinggian[3] < ketinggian[4] dan ketinggian[0] < ketinggian[4].
  • Dalam pertanyaan kelima, Alice boleh terus bergerak ke bangunan Bob sejak ketinggian[1] < ketinggian[6].
  • Untuk ans[i] != -1, Ia boleh ditunjukkan bahawa ans[i] ialah bangunan paling kiri tempat Alice dan Bob boleh bertemu.
  • Untuk jawapan[i] == -1, Ia boleh ditunjukkan bahawa tiada bangunan di mana Alice dan Bob boleh bertemu.

Kekangan:

• 1 <= heights.length <= 5 * 10⁴
• 1 <= ketinggian[i] <= 10⁹
• 1 <= queries.length <= 5 * 10⁴
• pertanyaan[i] = [a_i, b_i]
• 0 <= a_i, b_i <= ketinggian.panjang - 1

Petunjuk:

1. Untuk setiap pertanyaan [x, y], jika x > y, tukar x dan y. Sekarang, kita boleh menganggap bahawa x <= y.
2. Untuk setiap pertanyaan [x, y], jika x == y atau ketinggian[x] < ketinggian[y], maka jawapannya ialah y kerana x ≤ y.
3. Jika tidak, kita perlu mencari indeks t terkecil supaya y < t dan ketinggian[x] < ketinggian [t]. Ambil perhatian bahawa ketinggian[y] <= ketinggian[x], jadi ketinggian[x] < ketinggian[t] ialah syarat yang mencukupi.
4. Untuk mencari indeks t bagi setiap pertanyaan, susun pertanyaan dalam tertib menurun y. Ulangi pertanyaan sambil mengekalkan timbunan monotonik yang boleh kita cari secara binari untuk mencari indeks t.

Penyelesaian:

Masalahnya memerlukan penentuan bangunan paling kiri tempat Alice dan Bob boleh bertemu memandangkan bangunan permulaan dan peraturan pergerakan mereka. Setiap pertanyaan melibatkan mencari titik pertemuan berdasarkan ketinggian bangunan. Ini mencabar kerana kekangan pergerakan dan keperluan untuk pengiraan yang cekap.

Perkara Penting

1. Alice dan Bob boleh berpindah ke bangunan lain jika ketinggiannya lebih tinggi daripada bangunan semasa.
2. Untuk setiap pertanyaan, cari titik pertemuan paling kiri yang sah, atau kembalikan -1 jika tiada bangunan sedemikian wujud.
3. Kekangan menuntut penyelesaian yang lebih baik daripada pendekatan O(n²) yang naif.

Pendekatan

1. Pemerhatian:

   • Jika a == b, Alice dan Bob sudah berada di bangunan yang sama.
   • Jika ketinggian[a] < heights[b], bangunan Bob ialah tempat pertemuan.
   • Jika tidak, cari indeks bangunan terkecil t > b di mana:
     • ketinggian[a] < ketinggian[t]
     • ketinggian[b] <= ketinggian[t] (kerana b sudah kurang daripada perbandingan ketinggian).

2. Pengoptimuman Menggunakan Tindanan Monotonic:

   • Sebuah Timbunan monotonik membantu dengan cekap menjejaki bangunan sah yang boleh dialihkan oleh Alice dan Bob. Bangunan ditambahkan pada tindanan dengan cara yang memastikan ketinggian berada dalam susunan yang berkurangan, membolehkan carian binari pantas.

3. Isih Pertanyaan:

   • Isih pertanyaan dalam tertib menurun b untuk memproses bangunan dengan indeks yang lebih besar dahulu. Ini memastikan bahawa kami membina tindanan dengan cekap semasa kami bergerak daripada indeks yang lebih tinggi ke lebih rendah.

4. Carian Binari pada Tindanan:

   • Untuk setiap pertanyaan, gunakan carian binari pada tindanan monoton untuk mencari indeks t terkecil yang memenuhi syarat.

Rancang

1. Isih pertanyaan berdasarkan yang lebih besar daripada dua indeks (b) dalam tertib menurun.
2. Lintas tatasusunan ke belakang sambil mengekalkan timbunan indeks yang sah monoton.
3. Untuk setiap pertanyaan, semak kes remeh (a == b atau ketinggian[a] < ketinggian[b]).
4. Untuk kes bukan remeh, gunakan tindanan untuk mencari bangunan paling kiri yang sah melalui carian binari.
5. Kembalikan hasil dalam susunan pertanyaan asal.

Langkah Penyelesaian

1. Pertanyaan Praproses:

   • Pastikan a <= b dalam setiap pertanyaan untuk konsistensi.
   • Isih pertanyaan mengikut b dalam tertib menurun.

2. Lelar Melalui Pertanyaan:

   • Kekalkan timbunan monoton semasa kita melintasi tatasusunan.
   • Untuk setiap pertanyaan:
     • Jika a == b, jawapannya ialah b.
     • Jika ketinggian[a] < ketinggian[b], jawapannya ialah b.
     • Jika tidak, gunakan tindanan untuk mencari indeks sah terkecil t > b.

   • Carian Binari pada Tindanan:

     • Gunakan carian binari untuk mencari indeks terkecil t dengan cepat pada tindanan yang memenuhi ketinggian[t] > ketinggian[a].

   • Pulihkan Pesanan Asal:

     • Peta hasil kembali ke indeks pertanyaan asal.

   • Keputusan Pulangan.

   Mari laksanakan penyelesaian ini dalam PHP: 2940. Cari Bangunan Tempat Alice dan Bob Boleh Bertemu
   

   <?php
   /**
    * @param Integer[] $heights
    * @param Integer[][] $queries
    * @return Integer[]
    */
   function leftmostBuildingQueries($heights, $queries) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
   }
   
   /**
    * @param $queries
    * @return array
    */
   private function getIndexedQueries($queries) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
   }
   
   /**
    * @param $stack
    * @param $a
    * @param $heights
    * @return mixed|null
    */
   private function findUpperBound($stack, $a, $heights) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
   }
   
   class IndexedQuery {
       public $queryIndex;
       public $a; // Alice's index
       public $b; // Bob's index
   
       /**
        * @param $queryIndex
        * @param $a
        * @param $b
        */
       public function __construct($queryIndex, $a, $b) {
           $this->queryIndex = $queryIndex;
           $this->a = $a;
           $this->b = $b;
       }
   }
   
   // Test the function
   $heights = [6, 4, 8, 5, 2, 7];
   $queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];
   print_r(leftmostBuildingQueries($heights, $queries));
   
   $heights = [5, 3, 8, 2, 6, 1, 4, 6];
   $queries = [[0, 7], [3, 5], [5, 2], [3, 0], [1, 6]];
   print_r(leftmostBuildingQueries($heights, $queries));
   ?>
   

   Penjelasan:

   1. Isih Pertanyaan: Pertanyaan diisih mengikut b dalam tertib menurun untuk memproses indeks yang lebih besar dahulu, yang membolehkan kami mengemas kini tindanan monotonik kami semasa kami memproses.
   2. Timbunan Monotonic: Timbunan digunakan untuk menjejaki membina indeks di mana Alice dan Bob boleh bertemu. Kami hanya menyimpan bangunan yang mempunyai ketinggian lebih besar daripada bangunan yang dilihat sebelum ini dalam timbunan.
   3. Carian Perduaan: Apabila menjawab setiap pertanyaan, kami menggunakan carian binari untuk mencari indeks terkecil t dengan cekap di mana syarat dipenuhi.

   Contoh Panduan

   Input:

   • ketinggian = [6,4,8,5,2,7]
   • pertanyaan = [[0,1],[0,3],[2,4],[3,4],[2,2]]

   Proses:

   1. Isih Pertanyaan:

      • Pertanyaan diindeks: [(2,4), (3,4), (0,3), (0,1), (2,2)]

   2. Bina Tindanan Monotonic:

      • Mulakan pada indeks tertinggi dan tambahkan indeks pada timbunan:
        • Pada indeks 5: Tindanan = [5]
        • Pada indeks 4: Tindanan = [5, 4]
        • ...

   3. Pemprosesan Pertanyaan:

      • Untuk pertanyaan [0,1], ketinggian[0] < ketinggian[1]: Keputusan = 2.
      • ...

   Output:

   [2, 5, -1, 5, 2]

   Kerumitan Masa

   1. Isih Pertanyaan: O(Q log Q) dengan Q ialah bilangan pertanyaan.
   2. Pembinaan Tindanan Monotonik: O(N) dengan N ialah panjang ketinggian.
   3. Carian Perduaan untuk Setiap Pertanyaan: O(Q log N).

   Keseluruhan: O(N Q log (Q N)).

   Output sebagai Contoh

   Input:
   

   $heights = [6, 4, 8, 5, 2, 7];
   $queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];
   

   Output:
   

   print_r(findBuilding($heights, $queries)); // [2, 5, -1, 5, 2]
   

   Pendekatan ini mengendalikan kekangan besar dengan cekap dengan memanfaatkan timbunan monoton dan carian binari. Ia memastikan pemprosesan pertanyaan yang optimum sambil mengekalkan ketepatan.

   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 Cari Bangunan Tempat Alice dan Bob Boleh Bertemu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!