Remove K Digits

Q: Apa kompleksitas waktu dari Remove K Digits?

Dengan stack monotonik, proses ini berjalan dalam waktu O(n) untuk n digit: setiap digit didorong satu kali, dan setiap operasi pop menggunakan satu dari k penghapusan. Stack menampung hingga n digit, jadi ruang tambahan yang digunakan adalah O(n) . Memindai ulang dari kiri untuk setiap penghapusan membutuhkan waktu O(n·k) .

SedangMonotonic stack Greedy

+10

Kamu mendapatkan bilangan non-negatif yang ditulis sebagai string digit, num, dan bilangan bulat k. Hapus tepat k digit dan pertahankan urutan digit lainnya, sehingga bilangan yang tersisa sekecil mungkin.

Kembalikan hasilnya sebagai string tanpa nol di depan. Jika tidak ada yang tersisa, atau yang tersisa hanya nol, kembalikan "0".

Fungsi

removeKdigits(num: string, k: integer) → string

numstring: angka, ditulis sebagai string yang terdiri dari digit
kinteger: berapa banyak digit yang harus dihapus
Mengembalikanstring: angka terkecil yang dapat kamu sisakan, sebagai string tanpa nol di depan

Batasan

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num hanya berisi digit 0 sampai 9.
num tidak memiliki angka nol di depan, kecuali jika nilainya adalah angka nol itu sendiri, "0".

Contoh

Input: num = "4325043"k = 3
Output: "2043"
Penjelasan: Menghapus angka 4 dan angka 3 pertama menempatkan angka 2 di depan. Angka 0 tidak bisa berada di depan: ada empat digit sebelumnya dan kamu memiliki tiga penghapusan. Penghapusan terakhir mengambil angka 5, yang berada sebelum angka 0 yang lebih kecil.

Input: num = "30200"k = 1
Output: "200"
Penjelasan: Menghapus angka 3 menyisakan 0200, dan tanpa nol di depannya, nilainya adalah 200. Penghapusan lainnya mempertahankan angka 3 di depan dan menyisakan angka empat digit seperti 3000.

Input: num = "52"k = 2
Output: "0"
Penjelasan: Kedua digit dihapus, jadi tidak ada yang tersisa dan jawabannya adalah "0".

Pertanyaan lanjutan

Bagaimana kamu akan mengubah solusi untuk menghapus k digit dan menyisakan bilangan terbesar?

Petunjuk

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

0 dari 3 dibuka

Solusi

Digit paling kiri memiliki bobot terbesar, jadi digit pertama yang lebih besar daripada digit di sebelah kanannya harus dihapus. Tumpukan digit yang kamu pertahankan menerapkan aturan itu pada seluruh string dalam satu kali lintasan. Penghapusan yang tersisa dilakukan dari bagian belakang, lalu nol di depan dihapus terakhir.

Hapus satu digit setiap kali

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Hapus satu digit setiap kali: temukan posisi pertama i saat num[i] > num[i+1], lalu hapus num[i], atau hapus digit terakhir jika urutan digit tidak pernah menurun. Ulangi k kali.

Setiap jawaban memiliki n-k digit, jadi posisi pertama tempat dua jawaban berbeda menentukan mana yang lebih kecil. Hingga posisi i, digit tidak pernah menurun, jadi menghapus digit yang lebih awal akan menggeser digit yang nilainya setidaknya sama besarnya; menghapus digit yang lebih akhir akan membiarkan num[i] yang besar tetap di tempatnya. Menghapus num[i] menurunkan posisi paling awal yang bisa diturunkan.

Setiap penghapusan memindai ulang dari kiri dan menggeser digit setelahnya, jadi pekerjaannya adalah O(n·k). Pada 40,000 digit satu dengan k = 25,000, pemindaian membaca sekitar 6.9 × 10^8 digit.

Algoritma

Salin digit-digit ke dalam list yang bisa kamu hapus elemennya.
Ulangi sebanyak k kali: telusuri dari kiri sampai menemukan digit pertama yang lebih besar daripada digit berikutnya, atau sampai digit terakhir, lalu hapus digit tersebut.
Hapus angka nol di awal, lalu kembalikan "0" jika tidak ada yang tersisa.

def removeKdigits(num, k):
    digits = list(num)
    for _ in range(k):
        # Find the first digit that is bigger than the digit after it.
        # If the digits never go down, i stops on the last digit.
        i = 0
        while i + 1 < len(digits) and digits[i] <= digits[i + 1]:
            i += 1
        del digits[i]
    result = "".join(digits).lstrip("0")
    return result if result else "0"

Stack monotonik dari digit yang dipertahankan

Intuisi

Setelah versi lambat menghapus num[i], digit sebelum i tetap tidak pernah menurun, jadi penghapusan berikutnya hanya bisa dimulai dari digit sebelum celah. Stack menyimpan awalan itu: digit-digit yang dipertahankan, yang nilainya tidak pernah menurun dari bawah ke atas. Saat digit baru lebih kecil daripada digit teratas, digit teratas lebih besar daripada tetangga kanannya, yaitu digit yang akan dihapus oleh versi lambat. Hapus digit teratas, gunakan satu penghapusan, lalu terus hapus selama digit teratas yang baru masih lebih besar.

Pada 4325043 dengan k = 3, digit 3 menghapus digit 4, digit 2 menghapus digit 3, dan digit 0 menghapus digit 5. Digit 4 dan 3 dimasukkan ke stack saat muncul, sehingga hasilnya 2043.

Setiap digit dimasukkan ke stack satu kali dan setiap penghapusan menggunakan satu dari k penghapusan, jadi proses ini berjalan dalam O(n).

Algoritma

Buat stack digit kosong.
Untuk setiap digit dari num: selama masih ada penghapusan dan digit teratas stack lebih besar daripada digit tersebut, keluarkan digit teratas dan gunakan satu penghapusan. Lalu, tambahkan digit tersebut ke stack.
Jika masih ada penghapusan setelah perulangan, hapus sejumlah itu dari bagian atas stack.
Baca stack dari bawah ke atas, lewati nol di depan, lalu kembalikan sisanya, atau "0" jika tidak ada yang tersisa.

def removeKdigits(num, k):
    stack = []  # kept digits, never decreasing from bottom to top
    for digit in num:
        # A bigger digit right before a smaller one: dropping it makes the number smaller.
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # The kept digits never decrease, so any removals left come off the end.
    stack = stack[:len(stack) - k]
    result = "".join(stack).lstrip("0")
    return result if result else "0"

Jebakan dan kasus tepi

Mengeluarkan elemen dari stack saat elemen teratas sama dengan digit baru. Pada 112 dengan k = 1, hasilnya 12; jawaban yang benar adalah 11.
Lupa menghapus sisa elemen setelah perulangan, atau menghapusnya dari bagian depan. Stack tidak pernah berkurang, jadi digit terakhirnya tetap: 123456789 dengan k = 3 menghasilkan 123456.
Menghitung nol yang dihilangkan sebagai penghapusan. Pada 100200 dengan k = 1, hanya 1 yang dihapus; nol di bagian depan dihilangkan tanpa mengurangi jatah penghapusan, dan jawabannya adalah 200.
Mengembalikan string kosong. 10 dengan k = 1 hanya menyisakan nol, jadi jawabannya adalah "0".
Mengubah num menjadi bilangan bulat. Jumlah digitnya bisa mencapai 4 × 10^4, jauh melampaui kapasitas tipe bilangan bulat apa pun, jadi bandingkan digit sebagai karakter.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Remove K Digits?

Dengan stack monotonik, proses ini berjalan dalam waktu O(n) untuk n digit: setiap digit didorong satu kali, dan setiap operasi pop menggunakan satu dari k penghapusan. Stack menampung hingga n digit, jadi ruang tambahan yang digunakan adalah O(n). Memindai ulang dari kiri untuk setiap penghapusan membutuhkan waktu O(n·k).

Bagaimana cara menangani angka nol di depan dalam Remove K Digits?

Hapus digit terlebih dahulu, lalu hilangkan nol hanya di bagian akhir. Nol di depan tidak mengubah nilainya, jadi tidak perlu dihapus: 10200 dengan k = 1 menjadi 0200 lalu 200. Jika setelah menghilangkan nol tidak tersisa apa pun, kembalikan "0".

Bisakah Can Remove K Digits diselesaikan dengan ruang tambahan O(1)?

Ya, jika kamu boleh mengubah input. Stack tidak pernah menyimpan digit lebih banyak daripada yang sudah kamu baca, jadi stack dapat berada di bagian depan array digit itu sendiri, dengan satu indeks untuk bagian teratasnya. Bahasa dengan string yang tidak dapat diubah tetap memerlukan satu salinan digit, yaitu O(n).

def removeKdigits(num, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

num = "4325043"
k = 3

Output yang diharapkan

"2043"