. Tanjakan Lebar Maksimum

962. Tanjakan Lebar Maksimum

Kesukaran: Sederhana

Topik: Tatasusunan, Tindanan, Tindanan Monotonic

A tanjakan dalam nombor tatasusunan integer ialah pasangan (i, j) yang mana i < j dan angka[i] <= angka[j]. lebar tanjakan sedemikian ialah j - i.

Diberikan nombor tatasusunan integer, kembalikan lebar maksimum tanjakan dalam nombor. Jika tiada ramp dalam angka, kembalikan 0.

Contoh 1:

• Input: nombor = [6,0,8,2,1,5]
• Output: 4
• Penjelasan: Tanjakan lebar maksimum dicapai pada (i, j) = (1, 5): nums[1] = 0 dan nums[5] = 5.

Contoh 2:

• Input: nombor = [9,8,1,0,1,9,4,0,4,1]
• Output: 7
• Penjelasan: Tanjakan lebar maksimum dicapai pada (i, j) = (2, 9): nums[2] = 1 dan nums[9] = 1.

Kekangan:

• 2 <= nums.length <= 5 * 10⁴
• 0 <= angka[i] <= 5 * 10⁴

Penyelesaian:

Kita boleh memanfaatkan konsep tindanan monotonik. Inilah penyelesaian dan penjelasannya:

Pendekatan:

1. Timbunan Menurun Monotonic: Kami mencipta tindanan yang menjejaki indeks unsur dengan cara yang nums[timbunan[i]] berada dalam susunan yang berkurangan. Ini membolehkan kita mencari pasangan (i, j) kemudian di mana nums[i] <= nums[j].
2. Melintasi dari Hujung: Selepas mencipta tindanan, kami melintasi tatasusunan dari hujung (j dari n-1 hingga 0) untuk mencuba dan mencari i terjauh bagi setiap j di mana nums[i] <= nombor[j].
3. Kemas kini Lebar Maksimum: Apabila nums[i] <= nums[j] bertahan untuk bahagian atas tindanan semasa, hitung lebar tanjakan j - i dan kemas kini lebar maksimum jika ia lebih besar.

Mari laksanakan penyelesaian ini dalam PHP: 962. Tanjakan Lebar Maksimum

  
  
  Penjelasan:




Buat Tindanan Berkurangan:


Lelaran melalui tatasusunan dan tambahkan indeks pada tindanan.
Hanya tambahkan indeks jika ia sepadan dengan nilai yang kurang daripada atau sama dengan nilai indeks terakhir dalam tindanan. Ini memastikan bahawa nilai dalam tindanan berada dalam susunan yang semakin berkurangan.



Rentas dari Hujung:


Apabila kita pergi ke belakang melalui tatasusunan, untuk setiap j, pop indeks i dari timbunan selagi nums[i] <= nums[j].
Kira lebar j - i dan kemas kini maxWidth.



Mengapa Ini Berfungsi:


Dengan mengekalkan timbunan indeks yang semakin berkurangan, kami memastikan bahawa apabila kami menemui a j dengan nilai yang lebih besar, ia boleh memberi kami lebar j yang lebih besar - i apabila i dikeluarkan daripada timbunan.



Kerumitan Masa:


Membina tindanan mengambil masa O(n) kerana setiap indeks ditolak sekali.
Perjalanan dari hujung dan indeks pop juga mengambil O(n) kerana setiap indeks muncul paling banyak sekali.
Secara keseluruhan, penyelesaian berjalan dalam masa O(n), yang cekap untuk saiz input sehingga 5 * 10^4.





  
  
  Output:



Untuk nombor = [6, 0, 8, 2, 1, 5], output ialah 4, sepadan dengan tanjakan (1, 5).
Untuk nombor = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1], output ialah 7, sepadan dengan tanjakan (2, 9).


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 . Tanjakan Lebar Maksimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!