Find Peak Element
array nums naik lalu turun: setiap nilai lebih besar daripada nilai sebelumnya hingga indeks tertentu, dan setiap nilai setelah indeks itu lebih kecil daripada nilai sebelumnya. Salah satu bagian bisa kosong, jadi array hanya bisa naik atau hanya turun. Nilai pada indeks belokan adalah puncaknya, satu-satunya nilai yang lebih besar daripada setiap tetangganya.
Kembalikan indeks puncaknya dalam waktu O(log n).
Fungsi
- numsinteger-array
- nilainya naik hingga mencapai satu puncak, lalu turun
- Mengembalikaninteger
- indeks puncaknya
Batasan
1 ≤ nums.length ≤ 5000-106 ≤ nums[i] ≤ 106nums[i] != nums[i+1]untuk setiapiyang valid.numsmeningkat secara ketat hingga satu indeks dan menurun secara ketat setelahnya, jadi hanya ada satu puncak.
Contoh
- Input
- nums = [2, 5, 9, 4, 1]
- Output
- 2
- Penjelasan
- Nilainya naik melalui 2, 5, dan 9, lalu turun melalui 4 dan 1. Titik baliknya ada di 9, indeks 2.
- Input
- nums = [8, 6, 3, -2]
- Output
- 0
- Penjelasan
- array hanya turun, jadi bagian pendakiannya kosong dan puncaknya adalah nilai pertama, 8 pada indeks 0.
- Input
- nums = [-7, -3, 0, 12, 40]
- Output
- 4
- Penjelasan
- array hanya naik, jadi puncaknya adalah nilai terakhir, 40 pada indeks 4. Nilai negatif tidak mengubah apa pun.
Pertanyaan lanjutan
Dalam kisi yang tidak memiliki dua sel bertetangga dengan nilai yang sama, puncak adalah sel yang lebih besar daripada hingga empat sel tetangganya. Bisakah kamu menemukannya tanpa membaca setiap sel?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Pilih indeks
midmana saja dan perhatikannums[mid+1]. Apa yang ditunjukkan arah langkah itu tentang lokasi puncaknya?Langkah naik hanya terjadi sebelum puncak, dan langkah turun hanya terjadi di puncak atau setelahnya. Jadi, satu perbandingan menyingkirkan salah satu sisi
mid.Pertahankan rentang yang selalu mencakup puncak. Saat bergerak ke atas, pindahkan
lokemid+1; jika tidak, pindahkanhikemid. Berhenti saat keduanya bertemu.
Solusi
Dengan satu puncak, nilai puncak adalah yang terbesar, jadi satu kali penelusuran dapat menemukannya dalam O(n). Untuk O(log n), bandingkan nums[mid] dengan nums[mid+1]: kemiringan di mid menunjukkan di sisi mana dari puncak posisinya, sehingga setiap langkah dapat mengurangi separuh rentang.
Berjalanlah sampai nilainya mulai menurun
Intuisi
Sebelum titik puncak, setiap nilai lebih kecil daripada nilai berikutnya, dan mulai dari titik puncak, setiap nilai lebih besar. Jadi, titik puncak adalah indeks pertama i yang memenuhi nums[i] > nums[i+1], atau indeks terakhir jika array hanya terus meningkat.
Jika titik puncak berada di akhir 5000 nilai, penelusuran membutuhkan 4999 perbandingan, sedangkan pencarian biner hanya membutuhkan 13.
Algoritma
- Untuk
idari 0 hinggan-2, bandingkannums[i]dengannums[i+1]. - Pada
ipertama saatnums[i]lebih besar, kembalikani. - Jika perulangan berakhir tanpa penurunan, kembalikan
n-1.
def findPeakElement(nums):
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return i # the first step down starts at the peak
return len(nums) - 1 # never went down: the last value is the peakPencarian biner pada kemiringan
Intuisi
Baca satu pasangan, nums[mid] dan nums[mid+1]. Langkah yang naik berarti array masih menanjak, yang pada array ini hanya terjadi sebelum puncak: puncak berada di mid+1 atau di sebelah kanannya. Langkah yang turun berarti kamu berada di puncak atau sudah melewatinya: puncak berada di mid atau di sebelah kirinya.
Pertahankan rentang [lo, hi] yang selalu memuat puncak. Langkah yang naik menggeser lo ke mid+1. Langkah yang turun menggeser hi ke mid, dengan tetap menyertakan mid karena indeks itu mungkin adalah puncak. Saat lo bertemu hi, satu indeks yang tersisa adalah puncaknya. Pembulatan nilai mid ke bawah membuatnya tetap di bawah hi, sehingga mid+1 selalu ada.
Dalam contoh pertama, mid = 2 melihat 9 > 4, jadi hi = 2; lalu mid = 1 melihat 5 < 9, jadi lo = 2, yaitu puncaknya. 5000 nilai memerlukan paling banyak 13 langkah.
Algoritma
- Tetapkan
lo = 0danhi = n-1. - Selama
lo < hi, ambilmid = lo + (hi - lo) / 2, lalu bulatkan ke bawah. - Jika
nums[mid] < nums[mid+1], tetapkanlo = mid + 1. - Jika tidak, tetapkan
hi = mid. - Kembalikan
lo.
def findPeakElement(nums):
lo, hi = 0, len(nums) - 1 # the peak is always inside [lo, hi]
while lo < hi:
mid = lo + (hi - lo) // 2 # mid < hi, so mid + 1 is a valid index
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # still climbing: the peak is to the right of mid
else:
hi = mid # going down: the peak is mid or to its left
return lo
Jebakan dan kasus tepi
- Mengatur
hi = mid - 1saat bergerak turun satu langkah. Dalam[2, 5, 9, 4, 1],midpertama adalah puncaknya, danhi = 1membuangnya. Pencarian mengembalikan 1. - Membandingkan dengan
nums[mid-1]saat membulatkanmidke bawah.midbisa bernilai 0, sehingga tidak ada tetangga di sebelah kiri. - Menggunakan rentang setengah terbuka dengan
hi = n.midbisa bernilain-1, dannums[mid+1]mengakses indeks di luar akhir, bahkan untuk satu nilai saja. - Lupa melakukan pergeseran di Lua dan R. Jawabannya tetap indeks berbasis 0, jadi posisi
idikembalikan sebagaii-1.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu dari Find Peak Element?
Pencarian biner berjalan dalam waktu O(log n) dan ruang O(1), paling banyak 13 langkah untuk 5000 nilai. Penelusuran dari kiri memiliki kompleksitas O(n), karena mungkin membaca setiap pasangan sebelum menemukan penurunan.
Apakah pencarian biner tetap berfungsi jika ada beberapa puncak?
Ya, selama nilai-nilai yang bersebelahan berbeda dan posisi di luar kedua ujung dianggap lebih rendah daripada setiap nilai. Algoritma ini mengembalikan satu puncak, tidak selalu yang tertinggi. Setelah nilai naik, nilainya harus mulai turun paling lambat di ujung rentang, dan titik perubahan pertama adalah puncak, jadi sisi yang dipertahankan pencarian selalu memiliki satu puncak.
Apakah puncak selalu merupakan nilai terbesar?
Dalam soal ini, ya: array naik hingga mencapai satu puncak lalu turun setelahnya, jadi tidak ada nilai lain yang lebih besar. Dalam versi dengan beberapa puncak, tidak demikian, karena setiap nilai yang lebih besar daripada kedua tetangganya dianggap sebagai puncak. Itulah sebabnya pencarian membandingkan nilai-nilai yang bersebelahan, bukan mencari nilai maksimum.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def findPeakElement(nums):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
nums = [2, 5, 9, 4, 1]
Output yang diharapkan
2