Sonraki büyük değer araması
Görev tanımı
Problem
Sana birbirinden farklı tam sayılardan oluşan bir nums listesi ve değerlerinin hepsi nums'ta bir yerde görünen bir queries listesi veriliyor. Her sorgu değeri için nums'ta onun sağındaki, ondan büyük ilk değeri bul; arkasından büyük bir değer gelmiyorsa -1. Cevapları sorgu sırasıyla döndür.
Örnekler
Input: nums = [4, 1, 3, 6, 2, 5], queries = [1, 3, 2, 6]
Output: [3, 6, 5, -1]
Neden: 1'i 3, 3'ü 6, 2'yi 5 izliyor; 6'dan sonraki hiçbir şey daha büyük değil
Input: nums = [5, 4, 3, 2, 1], queries = [4, 1]
Output: [-1, -1]
Neden: liste yalnız düşüyor, yani hiçbir değerin ardından büyüğü gelmiyor
Input: nums = [7], queries = [7]
Output: [-1]
Neden: edge case: tek bir değerin sağında hiçbir şey yok
İpuçları
0 / 3
Her sorgu konumundan sağa taramak işe yarar, ama birçok değer büyük bir şey için uzun süre beklediğinde karesel. nums üzerinde tek bir geçiş her değeri birden cevaplayabilir mi?
Hâlâ büyük bir değer bekleyen değerleri tut. Yeni bir değer geldiğinde ondan küçük bekleyen her değer cevabını az önce bulmuştur. Bekleyen değerler her zaman düşen bir blok oluşturur, bu yüzden küçükler tepededir.
nums'u bir stack'le dolaş. Stack'in tepesi mevcut değerden küçük olduğu sürece onu pop et ve mevcut değeri bir sözlükte onun cevabı olarak kaydet. Mevcut değeri push et. Son olarak her sorguya sözlükte varsayılanı -1 olacak şekilde bak.
- Hedef zaman
- O(n + q)
- Hedef alan
- O(n + q)
Kısıtlar
- nums holds distinct integers
- every query value appears in nums
Çözüm
Bir değer ilk büyük değer gelene kadar stack'te bekler ve o anda tepededir, çünkü ondan sonra push edilmiş ve hâlâ bekleyen her şey ondan küçüktür. Böylece soldan sağa tek bir geçiş her değeri tam cevabı ortaya çıktığında pop eder ve çifti bir sözlüğe (dict) kaydeder; sonda hâlâ stack'te olan da hiç cevap almamıştır. Sorgular o zaman düz aramalardır. Her değer en fazla bir kez push ve pop edilir; zaman O(n + q), alan O(n).
def next_greater_lookup(nums, queries):
answer = {}
stack = [] # waiting values, falling from bottom to top
for x in nums:
while stack and stack[-1] < x:
answer[stack.pop()] = x # x is the first larger value after it
stack.append(x)
return [answer.get(q, -1) for q in queries]
print(next_greater_lookup([4, 1, 3, 6, 2, 5], [1, 3, 2, 6])) # -> [3, 6, 5, -1]
print(next_greater_lookup([5, 4, 3, 2, 1], [4, 1])) # -> [-1, -1]
print(next_greater_lookup([7], [7])) # -> [-1]Kodda değil de fikirde mi takıldın? Monoton stack bunu anlatıyor.