Sliding Window Maximum
Kamu mendapatkan array berisi bilangan bulat nums dan ukuran jendela k. Jendela dengan k nilai berurutan dimulai dari ujung kiri dan bergerak ke kanan satu posisi setiap kali, hingga tepi kanannya berada pada nilai terakhir. Kembalikan nilai terbesar di dalam jendela pada setiap posisi, dari kiri ke kanan: n-k+1 nilai untuk array dengan panjang n.
Fungsi
- numsinteger-array
- array yang dilalui jendela
- kinteger
- jumlah nilai di setiap jendela
- Mengembalikaninteger-array
- nilai terbesar dari setiap jendela, dari jendela paling kiri hingga paling kanan
Batasan
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- Hasilnya menyimpan
nums.length-k+1nilai, satu untuk setiap jendela, berurutan dari kiri ke kanan.
Contoh
- Input
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- Output
- [12, 12, 12, 8, 8]
- Penjelasan
- 12 berada di dalam tiga jendela pertama, jadi masing-masing menjawab 12. Setelah 12 bergeser keluar,
[3, 8, 5]dan[8, 5, 1]sama-sama memiliki 8 sebagai nilai terbesar.
- Input
- nums = [-3, -1, -7, -2]k = 2
- Output
- [-1, -1, -2]
- Penjelasan
- Jendela-jendelanya adalah
[-3, -1],[-1, -7], dan[-7, -2]. Bilangan negatif terbesar dari dua bilangan negatif adalah yang paling dekat dengan nol, sehingga hasilnya adalah -1, -1, dan -2.
- Input
- nums = [6, 6, 1]k = 3
- Output
- [6]
- Penjelasan
- Saat
ksama dengan panjang array, hanya ada satu jendela, yaitu seluruh array. Nilai terbesarnya adalah 6; salinan kedua dari 6 tidak menambahkan jawaban kedua.
Pertanyaan lanjutan
Bisakah kamu membuat queue yang mendukung penambahan nilai di bagian belakang, penghapusan nilai di bagian depan, dan pembacaan nilai maksimumnya saat ini, masing-masing dalam waktu amortisasi O(1)?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Memindai setiap jendela untuk mencari nilai terbesarnya memerlukan
klangkah per jendela. Bandingkan dua jendela yang bersebelahan: keduanya berbagik-1nilai, karena satu nilai keluar dari sisi kiri dan satu nilai masuk dari sisi kanan.Saat nilai baru masuk, setiap nilai lama di dalam jendela yang lebih kecil dari atau sama dengannya tidak akan pernah bisa menjadi nilai maksimum lagi. Nilai baru itu tetap ada di setiap jendela berikutnya yang masih memuat nilai lama tersebut, dan nilainya setidaknya sama besar. Kamu bisa membuang nilai-nilai lama itu untuk selamanya.
Pertahankan indeks nilai yang tersisa dalam antrean dua ujung, dengan nilainya selalu menurun secara ketat dari depan ke belakang. Untuk setiap indeks baru, keluarkan nilai yang lebih kecil atau sama dari bagian belakang, masukkan indeks tersebut, keluarkan bagian depan jika sudah bergeser keluar dari jendela, lalu baca nilai maksimum jendela di bagian depan.
Solusi
Jendela yang berdekatan berbagi k-1 nilai, jadi menghitung ulang nilai maksimum mengulangi hampir semua pekerjaan. Namun, nilai maksimum tidak bisa dibatalkan: saat nilai terbesar keluar dari jendela, kamu memerlukan nilai terbesar berikutnya tanpa membaca ulang jendela. Deque monotonik hanya menyimpan nilai yang masih bisa menjadi nilai maksimum, dengan jawabannya berada di bagian depan.
Pindai setiap jendela
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Baca nilai k dari setiap jendela dan simpan nilai terbesar. Setiap jendela dibaca secara lengkap, sehingga nilai maksimumnya tidak mungkin terlewat. Setiap jendela dari n-k+1 jendela memerlukan k kali pembacaan. Kasus terburuk terjadi saat k kira-kira setengah dari n: n = 2 × 10^4 dan k = 10^4 menghasilkan sekitar 10^4 jendela yang masing-masing berisi 10^4 nilai, atau 10^8 kali pembacaan.
Algoritma
- Lakukan perulangan dengan
startdari 0 hinggan-k. - Ambil nilai terbesar dari
nums[start]hingganums[start+k-1]. - Tambahkan nilai tersebut ke hasil, lalu kembalikan hasil setelah perulangan.
def maxSlidingWindow(nums, k):
result = []
for start in range(len(nums) - k + 1):
# Read all k values of this window again
result.append(max(nums[i] for i in range(start, start + k)))
return resultBlok dengan maksimum dari setiap sisi
Intuisi
Bagi array menjadi beberapa blok berukuran k: indeks 0 hingga k-1, lalu k hingga 2k-1, dan seterusnya, dengan blok terakhir yang lebih pendek jika k tidak membagi n secara merata. Sebuah jendela panjangnya tepat k, jadi jendela itu mencakup satu blok utuh atau bagian akhir satu blok ditambah bagian awal blok berikutnya.
Jadi, hitung terlebih dahulu fromStart[i], nilai terbesar dari awal blok milik i hingga i, dan toEnd[i], nilai terbesar dari i hingga akhir bloknya. Jendela yang dimulai pada i berakhir pada i+k-1: toEnd[i] mencakup bagian kirinya dan fromStart[i+k-1] mencakup bagian kanannya, jadi nilai yang lebih besar adalah nilai maksimumnya. Pada contoh pertama, jendela [2, 12, 3] mengambil toEnd[1] = 12 dan fromStart[3] = 3, sehingga hasilnya 12.
Tiga lintasan menghasilkan waktu O(n), dengan biaya dua array pembantu sepanjang n dan kebutuhan untuk memiliki seluruh array sebelum jawaban pertama.
Algoritma
- Isi
fromStartdari kiri ke kanan, mulai ulang dengannums[i]saatimerupakan kelipatank. - Isi
toEnddari kanan ke kiri, mulai ulang dengannums[i]pada indeks terakhir dan setiap kalii+1merupakan kelipatank. - Untuk setiap indeks awal
idari 0 hinggan-k, tambahkan nilai yang lebih besar antaratoEnd[i]danfromStart[i+k-1].
def maxSlidingWindow(nums, k):
n = len(nums)
# Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
from_start = [0] * n # max from the start of i's block up to i
to_end = [0] * n # max from i up to the end of i's block
for i in range(n):
if i % k == 0:
from_start[i] = nums[i]
else:
from_start[i] = max(from_start[i - 1], nums[i])
for i in range(n - 1, -1, -1):
if i == n - 1 or (i + 1) % k == 0:
to_end[i] = nums[i]
else:
to_end[i] = max(to_end[i + 1], nums[i])
# A window [i, i+k-1] is the tail of one block plus the head of the next.
return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]Deque indeks monotonik
Intuisi
Jika indeks j muncul sebelum i dan nums[j] ≤ nums[i], maka j tidak akan pernah lagi menjadi nilai maksimum: setiap jendela berikutnya yang memuat j juga memuat i, yang keluar lebih belakangan. Jadi, saat i tiba, kamu bisa melupakan j.
Simpan indeks yang belum dilupakan dalam deque. Saat i tiba, keluarkan indeks dari bagian belakang selama nilainya kurang dari atau sama dengan nums[i], lalu tambahkan i. Nilai yang tersisa menurun secara ketat dari depan ke belakang, sehingga bagian depan adalah nilai maksimum jendela. Simpan indeks, karena indeks di bagian depan juga harus keluar saat jendela melewatinya. Pada contoh pertama, di indeks 5 deque berisi 12, 8, dan 5; 12 berada di indeks 5 - 3 = 2, jadi 12 keluar dan jawabannya adalah 8.
Setiap indeks ditambahkan sekali dan dikeluarkan paling banyak sekali: paling banyak 2n operasi deque, dengan waktu O(n). Deque tidak pernah berisi lebih dari k indeks.
Algoritma
- Untuk setiap indeks
i, keluarkan indeks dari bagian belakang selama deque tidak kosong dan nilai di bagian belakangnya paling banyak sama dengannums[i]. - Tambahkan
ike bagian belakang. - Jika indeks di bagian depan sama dengan
i-k, indeks itu sudah keluar dari jendela: keluarkan. - Setelah
i ≥ k-1, tambahkan nilai pada indeks di bagian depan ke hasil.
from collections import deque
def maxSlidingWindow(nums, k):
window = deque() # indices; their values strictly decrease from front to back
result = []
for i, x in enumerate(nums):
# A value at the back that is not bigger than x can never be a maximum again.
while window and nums[window[-1]] <= x:
window.pop()
window.append(i)
# The front index has slid out of the window on the left.
if window[0] == i - k:
window.popleft()
# From index k-1 on, every step completes a window; its maximum sits at the front.
if i >= k - 1:
result.append(nums[window[0]])
return result
Jebakan dan kasus tepi
- Menyimpan nilai, bukan indeks. Dengan
[3, 1, 3]dank = 2, angka 3 yang kedua mengeluarkan angka 3 pertama, lalu dihapus karena nilainya sama dengannums[0], yaitu nilai yang sudah keluar. - Memberikan jawaban terlalu cepat atau terlalu lambat. Jendela penuh pertama berakhir pada indeks
k-1, dan hasilnya harus berisi tepatn-k+1nilai. - Mengeluarkan
i-k+1, bukani-k. Indeks tersebut masih merupakan nilai pertama dalam jendela. - Membaca bagian belakang deque tanpa memeriksa apakah isinya ada.
- Dalam pendekatan blok, lupa bahwa blok terakhir bisa lebih pendek dari
k. Pemindaian dari kanan ke kiri harus dimulai ulang di indeks terakhir serta di setiap akhir blok.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu dari Sliding Window Maximum?
Solusi deque monotonik berjalan dalam waktu O(n), karena setiap indeks dimasukkan sekali dan dikeluarkan paling banyak sekali. Deque menampung paling banyak k indeks, jadi ruang tambahan yang digunakan adalah O(k), di luar ruang untuk hasilnya.
Apakah Sliding Window Maximum dapat diselesaikan dengan heap?
Ya. Masukkan pasangan nilai dan indeks ke dalam max heap, lalu sebelum membaca elemen teratas, keluarkan elemen selama indeksnya berada di luar jendela. Operasi ini berjalan dalam waktu O(n log n) dan dapat menampung hingga n entri. Deque lebih cepat dan lebih kecil karena membuang nilai yang tidak berguna begitu nilai yang lebih besar tiba.
Apa perbedaan antara deque monotonik dan stack monotonik?
Bagian belakang deque bekerja seperti stack monotonik: sebelum kamu menambahkan nilai, kamu mengeluarkan nilai yang menjadi tidak berguna karenanya. Deque menambahkan jalan keluar di bagian depan untuk nilai yang sudah terlalu lama. Elemen lebih besar berikutnya tidak memiliki masa kedaluwarsa, jadi hanya membutuhkan stack. Balik perbandingannya, dan deque akan memberikan nilai minimum untuk setiap window.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def maxSlidingWindow(nums, k):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
Output yang diharapkan
[12, 12, 12, 8, 8]