Wawancara Coding: Menyelesaikan Next Greater Element II dengan Monotonic Stack

Apa yang dievaluasi oleh pewawancara

Diberikan sebuah array bilangan bulat sirkular, kembalikan nilai pertama yang lebih besar secara ketat yang ditemui searah jarum jam untuk setiap elemen, atau -1 jika tidak ada. Input dapat berisi duplikat, urutan monotonik, atau semua nilai yang sama.

Batasan dan kasus batas

“Lebih besar” bersifat ketat (strict); nilai yang sama tidak dapat menyelesaikan suatu indeks.
Indeks i mencari dari i+1 hingga n-1, lalu berputar kembali ke 0.
Setiap posisi menerima paling banyak satu jawaban; lintasan kedua tidak boleh menimpa hasil yang sudah terselesaikan.
Targetkan waktu O(n) dan ruang tambahan O(n).

Kerangka jawaban 30 detik

“Saya mempertahankan sebuah stack menurun dari indeks-indeks yang masih menunggu nilai yang lebih besar. Saya memindai array virtual yang digandakan: nilai saat ini yang lebih besar secara ketat akan melakukan pop dan menyelesaikan entri stack; indeks hanya dimasukkan selama lintasan pertama, sedangkan lintasan kedua menyediakan kandidat putaran sirkular. Setiap indeks di-push dan di-pop paling banyak satu kali, sehingga algoritmanya bersifat linier.”

Menyimpan posisi yang menunggu jawaban

Simpan indeks daripada nilai agar algoritma dapat menulis hasil dan mempertahankan posisi duplikat. Pertahankan nilai tidak meningkat dari dasar stack ke puncak. Nilai saat ini yang lebih besar akan menyelesaikan setiap nilai tunggu yang lebih kecil yang dapat di-pop olehnya.

Mengubah putaran sirkular menjadi pemindaian terbatas

Baca nums[i % n] untuk i dari 0 hingga 2n-2. Ketika i berada di bawah n, push indeks setelah menyelesaikan entri lama; pada kunjungan kedua, gunakan hanya untuk menyelesaikan sisa stack. Ini menghindari penyalinan array dan mencegah loop tak terbatas.

Menangani perbandingan ketat dan duplikat

Lakukan pop hanya ketika nums[current] > nums[stackTop]. Lebih besar atau sama dengan akan secara keliru membiarkan nilai yang sama saling menyelesaikan satu sama lain; lebih kecil dari akan merusak invarian menurun. Indeks yang belum terselesaikan tetap mempertahankan nilai awal -1.

Pertanyaan klarifikasi sebelum menjawab

Apakah “berikutnya” harus lebih besar secara ketat? Mengizinkan lebih besar atau sama dengan akan mengubah kondisi pop dan perilaku terhadap duplikat.
Bisakah array berupa array kosong? Tentukan bentuk nilai kembalian sebelum mengimplementasikan.
Apakah hasilnya harus berisi nilai atau indeks? Jarak dan indeks memerlukan perhitungan putaran sirkular yang berbeda.

Pembahasan mendalam langkah demi langkah

Inisialisasi setiap hasil ke -1 dan pertahankan stack kosong. Untuk posisi virtual i, atur index = i % n dan baca value = nums[index]. Pertama selesaikan indeks stack yang nilainya lebih kecil; ketika i berada di bawah n, push index karena ia belum mendapatkan pencarian searah jarum jam secara penuh. Lintasan kedua tidak pernah melakukan push, sehingga setiap indeks masuk tepat satu kali.

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 setelah berputar sirkular, sedangkan 2 tidak memiliki nilai yang lebih besar secara ketat. Indeks stack yang tersisa dengan benar mempertahankan -1.

Contoh jawaban berkualitas tinggi

“Saya menyimpan indeks yang belum menemukan jawaban dalam stack yang tidak meningkat. Saya secara logis memindai array dua kali dengan i % n; nilai saat ini yang lebih besar secara ketat daripada puncak stack akan melakukan pop dan menyelesaikan indeks tersebut. Saya me-push setiap indeks hanya pada kunjungan pertamanya, sehingga lintasan kedua menangani putaran sirkular tanpa duplikasi. Hasil dimulai pada -1, membuat array bernilai sama dan jawaban yang tidak ditemukan menjadi benar. Setiap indeks di-push dan di-pop paling banyak satu kali, menghasilkan waktu O(n) dan ruang O(n).”

Kesalahan umum

Menyalin array tiga kali untuk menangani sifat sirkular.
Me-push indeks kembali pada lintasan kedua, menyebabkan pekerjaan duplikat atau penimpaan nilai.
Menggunakan lebih besar atau sama dengan dan memperlakukan nilai yang sama sebagai lebih besar.
Memindai dari kanan tanpa menyatakan invarian stack, sehingga jawabannya bukan nilai pertama yang lebih besar.
Membiarkan hasil tidak terinisialisasi dan mencoba memperbaiki stack setelah pemindaian.

Gejala kegagalan dan perbaikannya

Jika [1,1,1] mengembalikan nilai selain -1, aturan kesetaraan salah. Jika 1 terakhir dalam [1,2,1] mengembalikan -1, putaran sirkular terlewatkan. Lacak indeks dan nilai stack serta pastikan bahwa setiap pop memiliki nilai saat ini yang lebih besar secara ketat.

Implementasi produksi

Gunakan tipe indeks yang cukup lebar untuk input. Hindari menyalin array saat memori terbatas. Untuk mengembalikan jarak, hitung (index - j + n) % n saat menyelesaikan indeks j, dan tentukan apakah jarak nol diizinkan.

Daftar periksa verifikasi

Uji input kosong, satu elemen, semua sama, meningkat ketat, menurun ketat, puncak berulang, dan array acak. Untuk input kecil, bandingkan dengan referensi O(n²) yang memindai searah jarum jam dari setiap indeks, menggunakan pengujian diferensial acak.

Pertanyaan lanjutan dan jawaban

Mengapa setiap indeks hanya dapat di-pop satu kali?

Setelah sebuah indeks melihat nilai pertama yang lebih besar secara ketat, indeks tersebut keluar dari stack. Elemen yang lebih jauh tidak bisa menjadi nilai pertama yang lebih besar. Setiap indeks masuk sekali dan keluar sekali, sehingga total operasi pop adalah O(n).

Apa yang berubah untuk kondisi lebih besar atau sama dengan?

Lakukan pop ketika nilai saat ini lebih kecil dari atau sama dengan puncak stack, lalu tentukan bagaimana nilai yang sama harus berperilaku di sepanjang array sirkular, termasuk apakah suatu elemen boleh menyelesaikan dirinya sendiri pada kunjungan berikutnya.

Bagaimana jika inputnya adalah stream berulang yang tak terbatas?

Jangan menunggu setiap posisi terselesaikan. Tetapkan jendela observasi terbatas atau batas waktu (timeout). Untuk array tetap, dua lintasan mencakup setiap kemungkinan kandidat berikutnya.

Rubrik penilaian

Invarian: menjelaskan bahwa stack menurun menyimpan indeks-indeks yang menunggu jawaban.
Penanganan sirkular: menggunakan dua lintasan terbatas tanpa menyalin atau melakukan loop selamanya.
Kasus batas duplikat: menggunakan perbandingan ketat dan mempertahankan nilai -1 yang belum terselesaikan.
Kompleksitas: memberikan waktu O(n) dan ruang tambahan O(n).
Verifikasi: menyertakan oracle O(n²) serta uji acak, duplikat, dan monotonik.

Pemeriksaan kepatuhan

Konfirmasikan bahwa invarian stack, batasan sirkular, dan klaim kompleksitas tetap konsisten.

Daftar periksa jawaban wawancara

Nyatakan bahwa indeks stack menunggu nilai yang lebih besar, lalu jelaskan i % n, dua lintasan, operasi pop yang ketat, satu push per indeks, dan kompleksitas yang diamortisasi.

Kesimpulan satu kalimat

Kueri next-greater sirkular menjadi linier dengan dua lintasan indeks dan sebuah monotonic stack menurun, sementara perbandingan ketat dan inisialisasi -1 mempertahankan semantik duplikat dan nilai yang tidak ditemukan.