Stock Span Problem
Kamu mendapatkan harga penutupan saham setiap hari: prices[i] adalah harga pada hari i. Rentang hari i adalah jumlah hari berturut-turut, yang berakhir pada hari i dan termasuk hari itu, saat harganya kurang dari atau sama dengan prices[i].
Kembalikan rentang setiap hari dalam urutan yang sama seperti prices. Setiap rentang minimal 1, karena satu hari selalu menghitung dirinya sendiri.
Fungsi
- pricesinteger-array
- harga pada setiap hari, secara berurutan
- Mengembalikaninteger-array
- rentang setiap hari, dalam urutan yang sama
Batasan
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- Hari sebelumnya dengan harga yang sama dihitung dalam rentang tersebut; hanya harga yang lebih tinggi yang menghentikannya.
Contoh
- Input
- prices = [31, 27, 14, 21, 30, 18, 40]
- Output
- [1, 1, 1, 2, 4, 1, 7]
- Penjelasan
- Hari ke-3 pada 21 melihat kembali ke 14 dan berhenti di 27: rentang 2. Hari ke-4 pada 30 berhenti di 31: rentang 4. Hari ke-6 pada 40 melampaui semua harga sebelumnya dan mencakup seluruh 7 hari.
- Input
- prices = [8, 8, 3, 8]
- Output
- [1, 2, 1, 4]
- Penjelasan
- Harga yang sama ikut dihitung, jadi hari ke-1 dengan harga 8 mencakup hari ke-0 dan mendapat 2. Hari ke-3 dengan harga 8 mencakup hari ke-3 dan kedua harga 8 sebelumnya, dengan rentang 4.
- Input
- prices = [50, 40, 30, 20]
- Output
- [1, 1, 1, 1]
- Penjelasan
- Setiap hari lebih murah daripada hari sebelumnya, jadi tidak ada rentang yang mencakup hari sebelumnya dan setiap rentang bernilai 1.
Pertanyaan lanjutan
Harga kini datang satu per satu, dan kamu harus melaporkan setiap rentang saat harganya tiba. Pendekatan mana yang masih berfungsi, dan apa yang disimpannya di antara pemanggilan?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Menghitung mundur dari setiap hari membuat pekerjaan berulang: jika harganya sama selama 8000 hari, hari terakhir saja harus menelusuri kembali 8000 hari. Saat kamu menelusuri mundur dari hari ini, hari-hari sebelumnya mana yang bisa kamu lewati selamanya?
Jika harga hari ini setidaknya sama tinggi dengan harga pada hari sebelumnya, hari sebelumnya itu tidak mungkin menjadi hari yang menghentikan rentang yang lebih panjang: hari ini lebih dekat dan harganya setidaknya sama mahal. Hanya hari-hari yang harganya lebih tinggi daripada semua hari setelahnya yang masih penting, dan harganya menurun dari yang paling lama ke yang terbaru.
Telusuri hari secara berurutan dan simpan hari-hari sebelumnya yang masih relevan di dalam stack, sebagai indeks. Sebelum menjawab untuk hari ini, keluarkan setiap hari yang harganya paling tinggi sama dengan harga hari ini. Stack kosong berarti rentangnya mencapai hari ke-0; jika tidak, rentangnya berhenti satu hari setelah hari yang tersisa di puncak. Lalu, masukkan hari ini ke dalam stack.
Solusi
Rentang suatu hari berakhir pada hari sebelumnya terdekat dengan harga yang lebih tinggi secara ketat. Menelusuri hari-hari sebelumnya untuk menemukannya membutuhkan hingga n langkah per hari. Sebagai gantinya, simpan hanya hari-hari yang masih bisa menghentikan rentang di masa mendatang: stack indeks dengan harga yang terus menurun akan menemukan setiap batas dalam satu kali lintasan.
Hitung mundur dari setiap hari
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Ikuti definisinya. Untuk hari i, mundur satu hari setiap kali selama harga pada hari itu tidak lebih dari prices[i], termasuk menghitung hari i. Harga pertama yang benar-benar lebih tinggi, atau awal array, mengakhiri penelusuran.
Tidak ada penelusuran yang menggunakan kembali penelusuran sebelumnya. Jika harga tetap atau naik, setiap penelusuran mundur hingga hari ke-0: n = 10^4 hari berarti sekitar 5 × 10^7 langkah.
Algoritma
- Buat
span, sebuah array yang panjangnya sama denganprices. - Untuk setiap hari
i, atur penghitung ke 0 dan pointerjkei. - Selama
j ≥ 0danprices[j] ≤ prices[i], tambahkan 1 ke penghitung dan mundurkanjsatu hari. - Simpan penghitung di
span[i]. Setelah hari terakhir, kembalikanspan.
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return spanTumpukan monotonik hari dengan nilai lebih tinggi
Intuisi
Sebut hari terdahulu terdekat dengan harga yang lebih tinggi secara ketat sebagai penghalang. Rentangnya adalah today - blocker, atau today + 1 jika tidak ada.
Pada contoh pertama, harga hari ke-3 adalah 21 dan harga hari ke-4 adalah 30. Setiap penelusuran berikutnya mencapai hari ke-4 terlebih dahulu, dan setiap harga yang melewati 30 juga melewati 21, jadi hari ke-3 tidak akan pernah bisa menjadi penghalang lagi. Secara umum, saat hari ini tiba, setiap kandidat terdahulu dengan harga paling tinggi sama dengan harga hari ini sudah selesai: keluarkan kandidat itu dari stack. Hari yang tersisa di puncak adalah penghalang untuk hari ini. Lalu, masukkan hari ini.
Harga pada stack turun secara ketat dari bawah ke atas, jadi harga pertama yang tersisa adalah harga lebih tinggi yang terdekat. Pada contoh pertama, hari ke-4 mengeluarkan hari ke-3 dan ke-1 dari stack, lalu berhenti di hari ke-0, sehingga rentangnya 4 - 0 = 4. Setiap hari dimasukkan sekali dan dikeluarkan paling banyak sekali, jadi proses ini berjalan dalam O(n).
Algoritma
- Buat array
spandan stack kosong untuk indeks hari. - Untuk setiap hari
today, keluarkan indeks dari stack selama harganya kurang dari atau sama denganprices[today]. - Jika stack kosong, span adalah
today + 1; jika tidak, span adalahtodaydikurangi indeks di posisi teratas. - Masukkan
todayke stack dan lanjutkan ke hari berikutnya. Kembalikanspan.
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
Jebakan dan kasus tepi
- Menghapus elemen saat
<, bukan<=. Dalam[8, 8, 3, 8], hari terakhir memiliki rentang 4; berhenti pada angka 8 sebelumnya menghasilkan 2. - Menulis
today, bukantoday + 1saat stack kosong. Hari 0 harus mendapat 1, bukan 0. - Hanya menghapus satu elemen per hari. Dalam contoh pertama, 40 harus melewati hari 5, 4, dan 0. Jika berhenti setelah hari 5, hari 4 terlihat seperti penghalangnya, sehingga rentangnya 2, bukan 7.
- Dalam Lua dan R, array dimulai dari 1. Dengan indeks berbasis 1, rentang saat stack kosong adalah
today, bukantoday + 1.
Pertanyaan yang sering diajukan4
Apa kompleksitas waktu dari masalah rentang harga saham?
Waktu O(n) dan ruang ekstra O(n) dengan stack monotonik, karena setiap hari keluar dari stack paling banyak satu kali. Menelusuri mundur dari setiap hari membutuhkan O(n²) ketika harga terus naik atau tetap sama.
Apakah stack harus menyimpan harga atau indeks hari?
Indeks hari. Span adalah jumlah hari, dan hanya indeks blocker yang memberimu informasi itu. prices[index] membaca kembali harga untuk perbandingan.
Apakah stock span problem dapat diselesaikan tanpa stack terpisah?
Ya. Mulai dari j = today - 1; selama j ≥ 0 dan prices[j] ≤ prices[today], lompat ke j - span[j], karena setiap hari dalam rentang tersebut memiliki harga paling tinggi prices[j]. Rentangnya adalah today - j. Lompatan hanya mendarat pada hari-hari yang akan disimpan oleh stack, jadi prosesnya tetap O(n).
Apakah masalah stock span termasuk masalah elemen yang lebih besar sebelumnya?
Ya, diukur dalam hari: untuk setiap hari, temukan hari sebelumnya yang paling dekat dengan harga yang lebih tinggi secara ketat, lalu laporkan jaraknya ke belakang. Balik arah pemindaian atau perbandingannya, dan stack yang sama akan memberikan nilai lebih besar berikutnya, nilai lebih kecil berikutnya, atau nilai lebih kecil sebelumnya.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def stockSpan(prices):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
prices = [31, 27, 14, 21, 30, 18, 40]
Output yang diharapkan
[1, 1, 1, 2, 4, 1, 7]