Longest Increasing Path in a Matrix
Satır listesi olarak, m satır ve n sütundan oluşan tam sayılardan oluşan bir ızgara olan matrix veriliyor. Bir yol yukarı, aşağı, sola veya sağa ilerler (çapraz hareket yoktur ve kenarlardan dolanılmaz) ve her adımda kesinlikle daha büyük bir değere ulaşılmalıdır. Böyle bir en uzun yoldaki hücre sayısını döndürün. Tek bir hücre, 1 hücrelik bir yoldur.
Fonksiyon
- matrixinteger-2d-array
- eşit uzunluktaki satırlardan oluşan bir liste olarak değerler ızgarası
- Döndürürinteger
- en uzun kesin artan yoldaki hücre sayısı
Kısıtlar
1 ≤ m, n ≤ 100; buradam = matrix.lengthven = matrix[i].length- Her satır aynı uzunluktadır
n. 0 ≤ matrix[i][j] ≤ 231-1
Örnekler
- Girdi
- matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
- Çıktı
- 7
- Açıklama
- 3, 4, 5, 6, 7, 8, 9 yolu sağ sütundan aşağı, alt satır boyunca ve orta sütundan yukarı 9'a kadar ilerler: 7 hücre. En küçük değer olan 1'den başlayınca en iyi yollar 5 hücreden oluşur.
- Girdi
- matrix = [[2, 2, 2], [2, 5, 2]]
- Çıktı
- 2
- Açıklama
- Eşit değerler bir adım yükselmek sayılmaz, bu yüzden hiçbir yol 2'lerin üzerinden ilerlemez. En iyisi, 5'in çevresindeki üç 2'den birinden 5'e adım atmaktır: 2 hücre.
- Girdi
- matrix = [[4, 4], [4, 4], [4, 4]]
- Çıktı
- 1
- Açıklama
- Her değer 4'tür, bu yüzden hiçbir yerde hiçbir adıma izin verilmez. Her hücre tek başına 1 hücrelik bir yoldur ve cevap 1'dir.
Ek soru
En uzun yollardan birinin uzunluğuyla birlikte hücrelerini de döndürebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir yol, daha önce ziyaret ettiği bir hücreye geri dönebilir mi? Yol boyunca değerlerin nasıl değiştiğini gözlemle.
Değerler yalnızca artar, bu nedenle bir yol hiçbir hücreyi tekrarlamaz ve bir hücrede başlayan en uzun yol, oraya nasıl ulaştığınıza bağlı değildir. Bu, daha büyük komşularının en iyisinden başlayan en uzun yolun 1 fazlasıdır.
Bu sayıyı her hücre için bir kez hesaplayıp saklayın. Ya kendi yığınınızı kullanarak daha büyük komşular üzerinde derinlik öncelikli aramayla doldurun ya da ızgarayı tepelerinden başlayarak her seferinde bir katman soyup katmanları sayın.
Çözüm
Her hücreden kendisinden büyük her komşuya bir ok çizin. Değerler her ok boyunca artar, dolayısıyla hiçbir ok zinciri döngü oluşturamaz: Izgara yönlü çevrimsiz bir çizgedir ve yanıt bu çizgedeki en uzun yoldur. Döngü olmadığında, bir hücreden başlayan en uzun yol yalnızca o hücreye bağlıdır; bu nedenle her hücre için bir kez hesaplama yaparsınız: O(m × n).
Her artan yolu takip edin
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her hücrede bir yürüyüş başlat ve daha büyük komşuların her dalını, devam edecek komşu kalmayana kadar takip et; en uzun yürüyüş cevaptır. Değerler her adımda artar, bu yüzden yürüyüş bir hücreye asla geri dönmez ve ziyaret edilen hücreler kümesine gerek duymaz.
Bir hücreden başlayan yürüyüş, başka bir yürüyüş her o hücreden geçtiğinde yeniden yapılır. Her değerin satırının ve sütununun toplamı olduğu 100 × 100 boyutundaki bir ızgarada, sağa veya aşağı atılan her adım tırmanış sağlar ve sol üst köşeden 10^58'den fazla yürüyüş çıkar.
Algoritma
- Her hücre için, yığına (hücre, 1) ekle.
- Bir (hücre, uzunluk) girdisi çıkar ve yanıtı uzunlukla güncelle.
- Izgara içindeki değeri kesin olarak daha büyük olan her komşu için (komşu, uzunluk + 1) ekle.
- Yığın boşalana kadar tekrarla, ardından sonraki başlangıç hücresine geç.
- Görülen en büyük uzunluğu döndür.
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
answer = 0
for sr in range(rows):
for sc in range(cols):
# Each entry is one path in progress: the cell it ends on and
# how many cells it has.
stack = [(sr, sc, 1)]
while stack:
r, c, length = stack.pop()
answer = max(answer, length)
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
stack.append((nr, nc, length + 1))
return answerkendi yığınınızla önbelleğe alınmış derinlik öncelikli arama
Sezgi
best[cell], oradan başlayan en uzun artan yoldaki hücre sayısı olsun: Daha büyük komşular nb için 1 + max(best[nb]); hiçbiri yoksa 1. Bunu saklamak güvenlidir, çünkü bir yoldaki cell hücresinden önce gelen hücrelerin tümü daha küçüktür ve ondan sonra gelemez. İlk örnekte 9 için 1, 8 için 2, 7 için 3, 6 ve 2 için 4, 5 ve 1 için 5, 4 için 6 ve 3 için 7 elde edilir.
Bir yol 10.000 hücrenin tümünden de geçebilir; bu, özyineleme için fazla derindir, bu yüzden kendi yığınınızı kullanın. En üstteki hücre sıradaki yönü dener ve henüz tamamlanmamış daha büyük bir komşuyu yığına ekler. Dört yönün tümü denendikten sonra hücreyi çıkarın ve best değerini ayarlayın. "İşleniyor" işaretine gerek yoktur: yığındaki her hücre, altındaki hücreden daha büyüktür.
Algoritma
- Her hücre için
bestdeğerini 0 (henüz bilinmiyor) ve yön sayacını 0 olarak ayarla. bestdeğeri 0 olan her hücreyi bir yığına ekle.- En üstteki hücrede sayacını ilerlet ve komşusu ızgaranın içindeyse, daha büyükse ve işlenmemişse onu yığına ekle.
- Dört yönü de kontrol ettikten sonra hücreyi yığından çıkar ve
bestdeğerini, daha büyük komşuları arasındaki en büyükbestdeğerinin 1 fazlası veya 1 olarak ayarla. - En büyük
bestdeğerini döndür.
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
# best[r][c]: cells on the longest increasing path that starts at (r, c).
# 0 means not known yet.
best = [[0] * cols for _ in range(rows)]
# step[r][c]: how many of the 4 directions the search has tried from (r, c).
step = [[0] * cols for _ in range(rows)]
answer = 0
for sr in range(rows):
for sc in range(cols):
if best[sr][sc]:
continue
# Our own stack instead of recursion: a path can be thousands of
# cells long, past Python's limit of 1,000 nested calls.
stack = [(sr, sc)]
while stack:
r, c = stack[-1]
d = step[r][c]
if d < 4:
step[r][c] = d + 1
nr, nc = r + dirs[d][0], c + dirs[d][1]
# The stack only climbs, so a larger neighbour is never on it.
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
stack.append((nr, nc))
continue
# Every larger neighbour is finished: build on the best of them.
stack.pop()
length = 1
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
length = max(length, best[nr][nc] + 1)
best[r][c] = length
answer = max(answer, length)
return answerIzgarayı zirvelerinden soy
Sezgi
Aynı tabloyu, Kahn'ın topolojik sıralamasındaki gibi en büyük değerlerden başlayarak oluştur. Bir tepe, yani daha büyük komşusu olmayan bir hücre, 1 hücrelik bir yol başlatır: 1. katman. Tüm tepeleri kaldır; son büyük komşusunu kaybeden hücreler bir sonraki katmana geçer. Izgara boşalana kadar tekrarla. Bir hücre, son büyük komşusundan bir tur sonra kaldırılır; dolayısıyla katmanı best değerine eşittir ve katman sayısı cevaptır. İlk örnekte katmanlar 9; 8; 7; 2 ve 6; 1 ve 5; 4; 3 şeklindedir.
Her hücre için, geriye kaç büyük komşusunun kaldığını say. Bir hücreyi kaldırmak, kendisinden kesin olarak küçük olan her komşusunun sayısını azaltır ve sayısı 0 olan hücre bir sonraki katmana eklenir. Her hücre bir kez kaldırılır: yığın kullanmadan O(m × n).
Algoritma
- Her hücre için, daha büyük değere sahip komşuların sayısını hesapla.
- Sayısı 0 olan her hücreyi mevcut katmana koy.
- Katman boş değilken katman sayısını 1 artır. Katmandaki her hücre için, kesin olarak daha küçük olan her komşunun sayısını azalt ve sayısı 0'a ulaşan bir komşuyu sonraki katmana koy.
- Sonraki katmanı mevcut katman yap ve tekrarla.
- Katman sayısını döndür.
def longestIncreasingPath(matrix):
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
# higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
higher = [[0] * cols for _ in range(rows)]
layer = []
for r in range(rows):
for c in range(cols):
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
higher[r][c] += 1
# A peak: no neighbour is larger, so a path from it has one cell.
if higher[r][c] == 0:
layer.append((r, c))
layers = 0
while layer:
layers += 1
next_layer = []
for r, c in layer:
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
higher[nr][nc] -= 1
# Its last larger neighbour is peeled: it is a peak now.
if higher[nr][nc] == 0:
next_layer.append((nr, nc))
layer = next_layer
# Each layer is one step further from a peak; the count is the longest path.
return layers
Tuzaklar ve uç durumlar
>=yerine>ile karşılaştırmak. Yan yana iki 4 olduğunda, kaba kuvvet yaklaşımı sonsuza kadar ileri geri gider; önbelleğe alınmış arama ise hâlâ hesaplanmakta olan bir uzunluğu okur.- Python'da özyineleme kullanmak. 100 × 100'lük bir ızgarada kıvrılarak ilerleyen değerler, varsayılan 1.000 çağrı sınırının on katı olan 10.000 hücrelik bir yol oluşturur.
- Tamamlanmış hücreleri, bir taşkın doldurma algoritmasının yapacağı gibi atlamak. Bu hücrelerde saklanan uzunluk, mevcut hücrenin tam olarak ihtiyaç duyduğu şeydir.
- Yalnızca en küçük değerden başlamak. İlk örnekte 1, 5 hücre verir; ancak yanıt olan 7, 3'ten başlar.
- Uzunlukları 0'dan başlatmak. Tüm değerleri eşit olan bir ızgaranın yanıtı 1'dir.
Sıkça sorulan sorular3
Bir Matristeki En Uzun Artan Yolun zaman karmaşıklığı nedir?
Ezberlemeli derinlik öncelikli aramayla veya katmanları soyarak O(m × n) zaman ve alan karmaşıklığı elde edilir: her hücre bir kez işlenir ve 4 komşusuna bakar. Her hücreden başlayan tüm yolları denemek üstel zaman alır.
Bir Matristeki En Uzun Artan Yol, dinamik programlama problemi midir yoksa grafik problemi mi?
Her ikisi de. Yönlü çevrimsiz bir grafikteki en uzun yoldur; bu, topolojik sıralama üzerinde dinamik programlamadır. Hücreleri en büyük değerden en küçüğe doğru sıralamak da geçerli başka bir sıralama sağlar; bunun bedeli sıralama için O(m × n × log(m × n))'dir.
Bu, en uzun artan alt diziden nasıl farklıdır?
Bir alt dizi bazı öğeleri atlayabilir ama sıralarını korur; buradaki bir yol, dört yönden herhangi birinde bitişik bir hücreye ilerlemelidir. Her iki durumda da kesin artan bir zincir kendi üzerine döngü yapamaz.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def longestIncreasingPath(matrix):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Beklenen Çıktı
7