Next Greater Element I
Birbirinden farklı tam sayılardan oluşan iki dizi, nums1 ve nums2 veriliyor ve nums1 içindeki her değer nums2 içinde de bulunuyor. Bir x değerinin sonraki daha büyük elemanı, nums2 içinde x'in sağında bulunan ve x'ten büyük olan ilk değerdir; böyle bir değer yoksa -1 olur.
nums1 içindeki her değerin sonraki daha büyük elemanını, nums1 sırasını koruyarak içeren bir dizi döndürün.
Fonksiyon
- nums1integer-array
- yanıtlanacak değerlerin tamamı nums2 içinde bulunur
- nums2integer-array
- her değerin sağ tarafına baktığınız dizi
- Döndürürinteger-array
- nums1'deki her değer için bir sonraki daha büyük eleman ya da -1; nums1'deki sırayla
Kısıtlar
1 ≤ nums1.length ≤ nums2.length ≤ 1040 ≤ nums1[i], nums2[i] ≤ 104-
nums1içindeki tüm değerler birbirinden farklıdır venums2içindeki tüm değerler birbirinden farklıdır. -
nums1değerlerinin her birinums2içinde bulunur.
Örnekler
- Girdi
- nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
- Çıktı
- [8, -1, 6]
- Açıklama
nums2içindeki 3'ten sonra 8 ve 2 gelir; 8, 3'ten büyük olan ilk sayıdır. 8'den sonra yalnızca 2 gelir, bu yüzden 8 -1 değerini alır. 1'in hemen ardından gelen değer 6'dır ve zaten daha büyüktür.
- Girdi
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- Çıktı
- [-1, 9]
- Açıklama
- 5'ten sonra yalnızca 4 gelir ve 4 daha küçüktür, bu yüzden 5 değeri -1 alır. 2'nin hemen ardından gelen değer 9'dur. Yanıtlar,
nums2sırasına göre değil,nums1sırasına göredir.
- Girdi
- nums1 = [10, 0]nums2 = [0, 10, 11]
- Çıktı
- [11, 10]
- Açıklama
- 10'dan sonraki ilk değer 11'dir. 0'dan sonraki ilk değer 10'dur ve bu daha büyüktür; bu nedenle 11 daha sonra gelip ondan da büyük olsa bile 0, 10'u alır.
Gönderirken +14 gizli test
Ek soru
nums2 öğesindeki her konum için, aynı tek geçişte bir sonraki daha büyük elemanının sağda kaç adım uzakta olduğunu döndürebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
nums1içindeki her değerin sağını taramak, değer başına 10^4 adıma kadar sürebilir. Yanıtlar yalnızcanums2'ye bağlıdır. Tek geçiştenums2içindeki her değerin sonraki daha büyük elemanını bulup ardındannums1değerlerini arayabilir misin?nums2dizisini soldan sağa tara ve henüz daha büyük bir değerle karşılaşmamış değerleri tut. Yeni bir değer geldiğinde, kendisinden küçük olan bekleyen her değer için yanıt olur. Bekleyen değerler her zaman azalan bir dizi oluşturur; bu nedenle küçük olanlar bir yığının üstünde bulunur.nums2içindeki her değer için: yığının en üstündeki değer ondan küçük olduğu sürece, en üstteki değeri çıkar ve mevcut değeri bir hash haritasında onun yanıtı olarak kaydet. Ardından mevcut değeri yığına ekle. Son olarak,nums1içindeki her değerin yanıtını haritadan bul; hiç çıkarılmamış bir değer için -1 kullan.
Çözüm
Tek bir değer için yanıt, sağa doğru yapılan bir taramadır; ancak nums1 içindeki her değer için tarama yapmak nums1.length × nums2.length adıma kadar maliyetlidir. Yanıtlar yalnızca nums2 değerlerine bağlıdır; bu nedenle monoton bir yığın kullanarak nums2 içindeki her değerin sonraki büyük elemanını tek seferde bulabilir, bunları bir hash haritasında tutabilir ve nums1 için arama yaparak yanıt verebilirsin.
Her değeri bul ve sağa doğru tara
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Tanımda söyleneni yapın. nums1 içindeki x değeri için nums2 içinde x'e ulaşana kadar ilerleyin. Ardından ilerlemeye devam edin ve x'ten büyük ilk değerde durun. Böyle bir değer bulamadan sona ulaşırsanız yanıt -1 olur.
Bu doğrudur çünkü tarama, x'in sağındaki değerleri sırayla ziyaret eder; dolayısıyla karşılaştığı ilk büyük değer, oradaki ilk büyük değerdir.
Yanıtlar uzaktaysa veya yoksa bu yöntem yavaştır. nums2 azalan sıradaysa hiçbir tarama daha büyük bir değer bulamaz ve nums1'deki her değer dizinin sonuna kadar ilerler. nums1'de m değer ve nums2'de n değer varsa bu, en fazla m × n adım demektir: her iki dizi de 10^4 değer içerdiğinde 10^8 adım. Ayrıca her tarama, önceki taramaların zaten geçtiği yerleri de yeniden tarar.
Algoritma
nums1içindeki herxdeğeri üzerinde döngü kur.nums2[j]değerininx'e eşit olduğujindeksini bul.nums2dizisinij+1'den başlayarak tara vex'ten büyük ilk değerde dur.- Bu değeri ekle; tarama dizinin sonuna ulaştıysa -1 ekle.
- Toplanan yanıtları döndür.
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 resultMonotonik yığın ve bir karma eşlemi
Sezgi
Soruyu tersine çevir. Her değer için ondan sonra ne geldiğini sormak yerine, nums2 üzerinde bir kez ilerle ve her yeni değerin, kendisinden küçük olan önceki değerleri yanıtlamasını sağla. Henüz yanıtı olmayan değerleri bir yığında tut. Bir değer geldiğinde, tepeden başlayarak kendisinden küçük olan tüm değerleri yığından çıkar: yeni değer, sağlarında bulunan ilk daha büyük değerdir ve dolayısıyla onların yanıtıdır. Ardından, hâlâ kendi yanıtını bekleyen yeni değeri yığına ekle.
nums2 = [1, 6, 3, 8, 2] üzerinden ilerle. 1'i ekle. Sonra 6 gelir ve 1'den büyüktür; bu nedenle 1, 6 ile eşleşir. 6'yı ekle. Ardından 3 gelir, 6'dan büyük değildir ve tepeye eklenir: yığın [6, 3] olur. Sonra 8, 3'ü ve 6'yı yığından çıkarır; ikisi de 8 ile eşleşir. 8'i ekle. Sonra 2 eklenir. Yığının son hâli [8, 2] olur ve bu iki değerin yanıtı yoktur. nums1 = [3, 8, 1] için eşleme [8, -1, 6] sonucunu verir.
Yığın, alttan üste doğru her zaman azalan sıradadır; çünkü bir değer, ancak üzerindeki kendisinden küçük tüm değerler yığından çıkarıldıktan sonra eklenir. Bu yüzden yalnızca tepeye bakman yeterlidir. Bir değer, ilk daha büyük değer göründüğü anda yığından çıkar; bu nedenle kaydettiğin yanıt en büyük değer değil, ilk karşılaşılan değerdir.
nums2'deki her değer yığına bir kez eklenir ve en fazla bir kez çıkarılır; bu nedenle iç döngü, tüm ilerleyiş boyunca toplamda en fazla n kez yığından değer çıkarır. m aramayla birlikte zaman karmaşıklığı O(n + m) olur. İki diziyi birbirine bağlayan şey eşlemedir: değerler birbirinden farklı olduğundan, nums1 ve nums2 içinde farklı konumlarda bulunsalar bile bir değer güvenli bir anahtardır. C ve R çözümleri, eşleme için değere göre indekslenen 10^4+1 hücreli bir dizi kullanır; bu yöntem, hiçbir değer 10^4'ü aşmadığı için işe yarar.
Algoritma
- Boş bir harita ve boş bir yığın oluştur.
nums2içindeki her değer için, yığının en üstündeki daha küçük değerleri çıkar ve bunları geçerli değerle eşleştir.- Geçerli değeri yığına ekle.
nums1içindeki her değer için, eşleştirilmiş yanıtını döndür; eşleşmesi yoksa -1 döndür.
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]
Tuzaklar ve uç durumlar
Yığın kodunun kendisi kısadır; hatalar, neyi kaydettiğinizde ve nereye baktığınızda ortaya çıkar.
- İlk büyük değer yerine sağdaki en büyük değeri kaydetmek.
nums2 = [3, 5, 1, 2, 4, 9, 0]içinde 1 için cevap 9 değil, 2'dir. - Cevapları
nums2sırasına göre veyanums2içindeki her değer için döndürmek. Sonuçta,nums1içindeki her değer için, onun sırasına göre bir giriş bulunur. - Değer yerine indeks döndürmek. Problem, büyük değerin kendisini ister.
nums2içinde, bir değerinnums1içindeki indeksinde arama yapmak. Aynı değer iki dizide farklı konumlarda bulunur; onu değerine göre bulun, harita bunun için vardır.- Sonda yığında kalan değerleri unutmak. Bu değerler daha büyük bir değerle karşılaşmadığından cevapları -1'dir; varsayılan değer olmadan haritada arama yapmak başarısız olur veya hiçbir şey döndürmez.
- Sola bakmak veya
nums2dizisinin başına dönmek. Yalnızca sağdaki değerler dikkate alınır ve dizi başa sarmaz.
Sıkça sorulan sorular4
Next Greater Element I'in zaman karmaşıklığı nedir?
Monotonik yığın çözümü O(n + m) zamanda çalışır; burada n, nums2 uzunluğunu ve m, nums1 uzunluğunu ifade eder. nums2 içindeki her değer en fazla bir kez yığına eklenir ve yığından çıkarılır; nums1 içindeki her değer için de haritada bir arama yapılır. Harita ve yığın O(n) alan kullanır. Her değerden başlayarak sağa doğru tarama O(n·m) zaman alır.
Monotonik yığın nedir?
Değerleri alttan üste doğru sıralı kalan bir yığındır; burada azalan sıradadır. Yeni bir değer eklemeden önce sıralamayı bozacak her şeyi yığından çıkarırsınız ve işte asıl işlem bu çıkarma sırasında gerçekleşir: çıkarılan her değer, sağındaki ilk daha büyük değeri bulmuştur. Bu yöntem, sonraki büyük, sonraki küçük ve benzeri soruları doğrusal zamanda çözer.
Next Greater Element I neden bir hash map'e ihtiyaç duyar?
Yığın taraması, yığından çıkan değerler sırasına göre, nums2 değerleriyle anahtarlanmış yanıtlar üretir. Çıktı, aynı değerlerin başka konumlarda bulunduğu nums1 sırasını izlemelidir. Tüm değerler birbirinden farklı olduğundan, değerden yanıta eşleme yapmak iki diziyi her değer için sabit zamanlı bir aramayla birbirine bağlar.
nums2 dairesel olursa ne değişir?
Ardından, daha büyük bir değer araması dizinin başından devam edebilir. i için 0'dan 2n-1'e kadar i % n indeksini kullanarak dizi üzerinde aynı yığın dolaşımını iki kez gerçekleştirin ve değerleri yalnızca ilk turda yığına ekleyin. Her iki turdan sonra hâlâ yığında olan değerlerin hiçbir yerde daha büyük bir değeri yoktur, bu nedenle cevapları -1'dir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def nextGreaterElement(nums1, nums2):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
Beklenen
[8, -1, 6]