Temuduga Pengekodan: Selesaikan Next Greater Element II dengan Tindanan Monotonik

Perkara yang dinilai oleh penemu duga

Diberi tatasusunan integer membulat, kembalikan nilai pertama yang lebih besar secara ketat yang ditemui mengikut arah jam bagi setiap elemen, atau -1 jika tiada. Input mungkin mengandungi pendua, jujukan monotonik, atau semua nilai yang sama.

Kekangan dan sempadan

“Lebih besar” adalah ketat; nilai yang sama tidak boleh menyelesaikan sesuatu indeks.
Indeks i mencari dari i+1 hingga n-1, kemudian membalut kembali ke 0.
Setiap kedudukan menerima paling banyak satu jawapan; laluan kedua tidak boleh menimpa hasil yang telah diselesaikan.
Sasarkan masa O(n) dan ruang tambahan O(n).

Rangka jawapan 30 saat

“Saya mengekalkan tindanan menurun bagi indeks yang masih menunggu nilai yang lebih besar. Saya mengimbas tatasusunan berganda secara maya: nilai semasa yang lebih besar secara ketat akan melenting (pop) dan menyelesaikan entri tindanan; indeks dimasukkan hanya semasa laluan pertama, manakala laluan kedua membekalkan calon balutan. Setiap indeks ditolak (push) dan dilenting (pop) paling banyak sekali, jadi algoritma ini adalah linear.”

Menyimpan kedudukan yang menunggu jawapan

Simpan indeks dan bukannya nilai supaya algoritma boleh menulis hasil dan mengekalkan kedudukan pendua. Kekalkan nilai tidak meningkat dari bawah tindanan ke atas. Nilai semasa yang lebih besar menyelesaikan setiap nilai menunggu yang lebih kecil yang boleh dilentingkannya.

Menukar balutan kepada imbasan bersempadan

Baca nums[i % n] untuk i dari 0 hingga 2n-2. Apabila i berada di bawah n, tolak indeks selepas menyelesaikan entri lama; pada lawatan kedua, gunakannya hanya untuk menyelesaikan tindanan yang tinggal. Ini mengelakkan penyalinan tatasusunan dan menghalang gelung tak terhingga.

Mengendalikan perbandingan ketat dan pendua

Lentingkan hanya apabila nums[current] > nums[stackTop]. Lebih besar atau sama dengan secara salah membenarkan nilai yang sama menyelesaikan antara satu sama lain; kurang daripada memecahkan invarians menurun. Indeks yang tidak diselesaikan mengekalkan nilai awal -1.

Soalan penjelasan sebelum menjawab

Adakah “seterusnya” lebih besar secara ketat? Membenarkan lebih besar atau sama dengan mengubah syarat lentingan dan tingkah laku pendua.
Bolehkah tatasusunan menjadi kosong? Tentukan bentuk pulangan sebelum melaksanakan.
Patutkah hasilnya mengandungi nilai atau indeks? Jarak dan indeks memerlukan pengiraan balutan yang berbeza.

Analisis mendalam langkah demi langkah

Mulakan setiap hasil kepada -1 dan kekalkan tindanan kosong. Untuk kedudukan maya i, tetapkan index = i % n dan baca value = nums[index]. Mula-mula selesaikan indeks tindanan yang nilainya lebih kecil; apabila i berada di bawah n, tolak index kerana ia belum mempunyai carian arah jam yang lengkap. Laluan kedua tidak pernah menolak, jadi setiap indeks masuk sekali sahaja.

text

result = [-1] * n
stack = []
for i in range(2 * n - 1):
    index = i % n
    while stack and nums[stack[-1]] < nums[index]:
        result[stack.pop()] = nums[index]
    if i < n:
        stack.append(index)

Untuk [1,2,1], elemen terakhir 1 melihat 2 selepas membalut, manakala 2 tidak mempunyai nilai yang lebih besar secara ketat. Baki indeks tindanan mengekalkan -1 dengan betul.

Model jawapan berkualiti tinggi

“Saya menyimpan indeks yang belum menemui jawapan dalam tindanan tidak meningkat. Saya mengimbas tatasusunan secara logik sebanyak dua kali dengan i % n; nilai semasa yang lebih besar secara ketat daripada bahagian atas tindanan akan melenting dan menyelesaikan indeks tersebut. Saya menolak setiap indeks hanya pada lawatan pertamanya, jadi laluan kedua mengendalikan balutan tanpa pertindihan. Hasil bermula pada -1, menjadikan tatasusunan yang sama dan jawapan yang tiada adalah betul. Setiap indeks ditolak dan dilenting paling banyak sekali, memberikan masa O(n) dan ruang O(n).”

Kesilapan biasa

Menyalin tatasusunan tiga kali untuk mengendalikan sifat membulat.
Menolak indeks sekali lagi dalam laluan kedua, menyebabkan kerja bertindih atau penimpaan.
Menggunakan lebih besar atau sama dengan dan menganggap nilai yang sama sebagai lebih besar.
Mengimbas dari kanan tanpa menyatakan invarians tindanan, menyebabkan jawapan bukan nilai lebih besar yang pertama.
Membiarkan hasil tidak dimulakan dan cuba membaiki tindanan selepas imbasan.

Gejala kegagalan dan pembetulan

Jika [1,1,1] mengembalikan nilai bukan -1, peraturan kesamaan adalah salah. Jika 1 terakhir dalam [1,2,1] mengembalikan -1, balutan telah ditinggalkan. Surih indeks dan nilai tindanan serta sahkan bahawa setiap lentingan mempunyai nilai semasa yang lebih besar secara ketat.

Pelaksanaan pengeluaran

Gunakan jenis indeks yang cukup luas untuk input. Elakkan menyalin tatasusunan apabila memori terhad. Untuk mengembalikan jarak, kira (index - j + n) % n apabila menyelesaikan indeks j, dan tentukan sama ada jarak sifar dibenarkan.

Senarai semak pengesahan

Uji input kosong, satu elemen, semua sama, meningkat ketat, menurun ketat, puncak berulang, dan tatasusunan rawak. Untuk input kecil, bandingkan dengan rujukan O(n²) yang mengimbas mengikut arah jam dari setiap indeks, menggunakan ujian pembezaan rawak.

Soalan susulan dan jawapan

Mengapakah setiap indeks hanya boleh dilentingkan sekali?

Sebaik sahaja sesuatu indeks melihat nilai pertamanya yang lebih besar secara ketat, ia meninggalkan tindanan. Elemen yang lebih jauh tidak boleh menjadi nilai lebih besar yang pertama. Setiap indeks masuk sekali dan keluar sekali, jadi jumlah operasi melenting ialah O(n).

Apakah yang berubah untuk lebih besar atau sama dengan?

Lentingkan apabila nilai semasa adalah kurang daripada atau sama dengan bahagian atas tindanan, kemudian tentukan bagaimana nilai yang sama harus bertindak di sekeliling bulatan, termasuk sama ada sesuatu elemen boleh menyelesaikan dirinya sendiri pada lawatan kemudian.

Bagaimana jika input ialah strim berulang yang tidak terhingga?

Jangan tunggu setiap kedudukan diselesaikan. Tetapkan tetingkap pemerhatian terhingga atau tamat masa (timeout). Untuk tatasusunan tetap, dua laluan meliputi setiap calon masa hadapan yang mungkin.

Rubrik pemarkahan

Invarians: menerangkan bahawa tindanan menurun memegang indeks yang menunggu jawapan.
Pengendalian membulat: menggunakan dua laluan bersempadan tanpa menyalin atau bergelung selama-lamanya.
Sempadan pendua: menggunakan perbandingan ketat dan mengekalkan nilai -1 yang belum diselesaikan.
Keperihalan: memberikan masa O(n) dan ruang tambahan O(n).
Pengesahan: merangkumi orakel O(n²) dan ujian rawak, pendua, serta monotonik.

Semakan pematuhan

Sahkan bahawa invarians tindanan, sempadan membulat, dan tuntutan keperihalan kekal konsisten.

Senarai semak jawapan temuduga

Nyatakan bahawa indeks tindanan menunggu nilai yang lebih besar, kemudian terangkan i % n, dua laluan, lentingan ketat, satu tolakan setiap indeks, dan keperihalan terlunas (amortized).

Rumusan satu ayat

Pertanyaan elemen lebih besar seterusnya secara membulat menjadi linear dengan dua laluan indeks dan tindanan monotonik menurun, manakala perbandingan ketat dan pemulaan -1 mengekalkan semantik pendua dan nilai yang hilang.