Next Greater Element I

Q: Apa kompleksitas waktu dari Next Greater Element I?

Solusi tumpukan monotonik berjalan dalam waktu O(n + m) , dengan n sebagai panjang nums2 dan m sebagai panjang nums1 , serta menggunakan ruang O(n) untuk map dan tumpukan. Memindai ke kanan dari setiap nilai membutuhkan waktu O(n·m) .

MudahMonotonic stack Hashing

+10

Kamu mendapatkan dua array berisi bilangan bulat yang berbeda, nums1 dan nums2, dan setiap nilai dalam nums1 juga muncul dalam nums2. Elemen lebih besar berikutnya dari suatu nilai x adalah nilai pertama di sebelah kanan x dalam nums2 yang lebih besar dari x, atau -1 jika tidak ada nilai seperti itu.

Kembalikan sebuah array yang berisi elemen lebih besar berikutnya dari setiap nilai dalam nums1, sesuai urutan dalam nums1.

Fungsi

nextGreaterElement(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: nilai-nilai yang harus dijawab, semuanya ditemukan di nums2
nums2integer-array: array yang di dalamnya kamu melihat ke sebelah kanan setiap nilai
Mengembalikaninteger-array: elemen lebih besar berikutnya dari setiap nilai nums1, atau -1, sesuai urutan nums1

Batasan

1 ≤ nums1.length ≤ nums2.length ≤ 10⁴
0 ≤ nums1[i], nums2[i] ≤ 10⁴
Semua nilai dalam nums1 berbeda, dan semua nilai dalam nums2 berbeda.
Setiap nilai nums1 muncul di nums2.

Contoh

Input: nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
Output: [8, -1, 6]
Penjelasan: Setelah angka 3 di nums2, ada 8 dan 2, dan 8 adalah angka pertama yang lebih besar. Setelah 8 hanya ada 2, jadi 8 mendapat nilai -1. Tepat setelah 1 ada 6, yang sudah lebih besar.

Input: nums1 = [5, 2]nums2 = [2, 9, 5, 4]
Output: [-1, 9]
Penjelasan: Hanya 4 yang mengikuti 5, dan nilainya lebih kecil, jadi 5 mendapat -1. Tepat setelah 2 muncul 9. Jawabannya mengikuti urutan nums1.

Pertanyaan lanjutan

Untuk setiap posisi nums2, bisakah kamu mengembalikan jumlah langkah ke kanan menuju elemen berikutnya yang lebih besar dengan satu kali lintasan yang sama?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Memindai ke kanan dari setiap nilai di nums1 mengulangi pekerjaan, dan jawabannya hanya bergantung pada nums2. Satu kali penelusuran dengan stack monoton menemukan elemen lebih besar berikutnya dari setiap nilai nums2 sekaligus. Hash map menyimpannya, lalu pencarian memberikan jawaban untuk nums1.

Temukan setiap nilai dan pindai ke kanan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Untuk setiap nilai x di nums1, cari x di nums2 lalu telusuri ke kanan sampai menemukan nilai pertama yang lebih besar, atau -1 jika sudah mencapai akhir. Penelusuran memeriksa nilai-nilai di sebelah kanan x secara berurutan, jadi nilai pertama yang lebih besar yang ditemukan adalah jawabannya.

Jika nums2 menurun, setiap penelusuran berjalan sampai akhir: hingga m × n langkah, yaitu 10^8 jika kedua array berisi 10^4 nilai.

Algoritma

Lakukan perulangan pada setiap nilai x dari nums1.
Temukan indeks j tempat nums2[j] sama dengan x.
Pindai nums2 mulai dari j+1 dan berhenti pada nilai pertama yang lebih besar dari x.
Tambahkan nilai tersebut, atau -1 jika pemindaian mencapai akhir.
Kembalikan jawaban yang terkumpul.

def nextGreaterElement(nums1, nums2):
    result = []
    for x in nums1:
        j = 0
        while nums2[j] != x:
            j += 1
        answer = -1
        for k in range(j + 1, len(nums2)):
            if nums2[k] > x:
                answer = nums2[k]
                break
        result.append(answer)
    return result

Stack monotonik dan hash map

Intuisi

Telusuri nums2 sekali dan biarkan setiap nilai baru menjawab nilai-nilai sebelumnya yang lebih kecil darinya. Simpan nilai yang masih menunggu jawaban di sebuah tumpukan. Saat sebuah nilai muncul, keluarkan setiap nilai yang lebih kecil dari bagian atas tumpukan, lalu petakan nilai tersebut ke nilai baru itu, yaitu nilai pertama yang lebih besar di sebelah kanannya. Kemudian, masukkan nilai baru itu ke tumpukan.

Tumpukan menurun dari bawah ke atas, karena sebuah nilai hanya dimasukkan setelah setiap nilai yang lebih kecil di atasnya dikeluarkan, jadi kamu hanya perlu melihat bagian atasnya. Sebuah nilai dikeluarkan begitu nilai pertama yang lebih besar muncul, jadi jawabannya adalah nilai pertama yang lebih besar, bukan nilai terbesar.

Pada [1, 6, 3, 8, 2], 6 mengeluarkan 1, lalu 8 mengeluarkan 3 dan 6, sementara 8 dan 2 berakhir tanpa jawaban. Setiap nilai dimasukkan sekali dan dikeluarkan paling banyak sekali, jadi dengan m pencarian, waktunya adalah O(n + m).

Algoritma

Buat map kosong dan stack kosong.
Untuk setiap nilai nums2, keluarkan setiap nilai yang lebih kecil dari bagian atas stack, lalu petakan ke nilai saat ini.
Masukkan nilai saat ini ke stack.
Untuk setiap nilai nums1, kembalikan jawaban yang dipetakan, atau -1 jika tidak ada.

def nextGreaterElement(nums1, nums2):
    next_greater = {}
    stack = []  # values still waiting for a greater one, decreasing from bottom to top
    for value in nums2:
        # value is the first greater value to the right of every smaller value on the stack.
        while stack and stack[-1] < value:
            next_greater[stack.pop()] = value
        stack.append(value)
    # Whatever is still on the stack has no greater value to its right.
    return [next_greater.get(x, -1) for x in nums1]

Jebakan dan kasus tepi

Mencatat nilai terbesar di sebelah kanan, bukan nilai pertama yang lebih besar. Dalam nums2 = [3, 5, 1, 2, 4, 9, 0], jawabannya untuk 1 adalah 2, bukan 9.
Mengembalikan jawaban sesuai urutan nums2. Hasilnya memiliki satu entri untuk setiap nilai nums1, sesuai urutannya: [-1, 9] pada contoh kedua.
Membaca nums2 pada indeks yang dimiliki suatu nilai di nums1. Pada contoh pertama, 3 berada di indeks 0 pada nums1, tetapi di indeks 2 pada nums2.
Melupakan nilai yang tersisa di stack. Jawabannya adalah -1, dan pencarian pada map tanpa nilai default akan gagal untuk nilai-nilai tersebut.

Pertanyaan yang sering diajukan4

Apa kompleksitas waktu dari Next Greater Element I?

Solusi tumpukan monotonik berjalan dalam waktu O(n + m), dengan n sebagai panjang nums2 dan m sebagai panjang nums1, serta menggunakan ruang O(n) untuk map dan tumpukan. Memindai ke kanan dari setiap nilai membutuhkan waktu O(n·m).

Apa itu stack monotonik?

Stack yang nilainya tetap terurut dari bawah ke atas. Sebelum kamu memasukkan nilai, keluarkan semua nilai yang akan merusak urutan, dan setiap nilai yang dikeluarkan adalah tempat jawaban ditemukan. Stack ini menyelesaikan soal tentang nilai lebih besar berikutnya, nilai lebih kecil berikutnya, dan soal serupa dalam waktu linear.

Mengapa Next Greater Element I memerlukan hash map?

Penelusuran stack menghasilkan jawaban yang dikaitkan dengan nilai nums2, sesuai urutan nilai tersebut keluar dari stack. Output mengikuti urutan nums1, tempat nilai yang sama berada di posisi lain. Semua nilai berbeda, jadi pemetaan dari nilai ke jawaban menghubungkan kedua array dengan satu pencarian berwaktu konstan untuk masing-masing nilai.

Apa yang berubah jika nums2 berbentuk melingkar?

Pencarian nilai yang lebih besar kemudian dapat dilanjutkan dari awal array. Jalankan penelusuran stack yang sama dua kali, dengan indeks i % n untuk i dari 0 hingga 2n-1, dan masukkan nilai ke stack hanya pada putaran pertama. Nilai yang masih berada di stack setelah kedua putaran tidak memiliki nilai yang lebih besar di mana pun, jadi jawabannya adalah -1.

def nextGreaterElement(nums1, nums2):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums1 = [3, 8, 1]
nums2 = [1, 6, 3, 8, 2]

Output yang diharapkan

[8, -1, 6]