Longest Increasing Path in a Matrix
Se te proporciona matrix, una cuadrícula de números enteros con m filas y n columnas, como una lista de filas. Un camino avanza hacia arriba, hacia abajo, a la izquierda o a la derecha (sin diagonales ni pasar de un borde al otro), y cada paso debe llegar a un valor estrictamente mayor. Devuelve el número de celdas del camino más largo de este tipo. Una sola celda es un camino de 1 celda.
Función
- matrixinteger-2d-array
- la cuadrícula de valores, como una lista de filas de igual longitud
- Devuelveinteger
- el número de celdas en la ruta estrictamente creciente más larga
Restricciones
1 ≤ m, n ≤ 100, dondem = matrix.lengthyn = matrix[i].length- Cada fila tiene la misma longitud
n. 0 ≤ matrix[i][j] ≤ 231-1
Ejemplos
- Entrada
- matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
- Salida
- 7
- Explicación
- El camino 3, 4, 5, 6, 7, 8, 9 baja por la columna de la derecha, sigue por la fila inferior y sube por la columna del medio hasta el 9: 7 celdas. Desde el valor más pequeño, 1, los mejores caminos tienen 5 celdas.
- Entrada
- matrix = [[2, 2, 2], [2, 5, 2]]
- Salida
- 2
- Explicación
- Los valores iguales no cuentan como un paso hacia arriba, así que ningún camino avanza por los 2. Lo mejor es dar un paso desde uno de los tres 2 que rodean al 5 hasta el 5: 2 celdas.
- Entrada
- matrix = [[4, 4], [4, 4], [4, 4]]
- Salida
- 1
- Explicación
- Todos los valores son 4, así que no se permite ningún paso en ninguna parte. Cada celda por sí sola es un camino de 1 celda, y 1 es la respuesta.
Para ir más allá
¿También puedes devolver las celdas de una de las rutas más largas, junto con su longitud?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
¿Puede un camino volver alguna vez a una celda que ya ha visitado? Observa qué hacen los valores a lo largo del recorrido.
Los valores solo aumentan, así que un camino nunca repite una celda, y el camino más largo que empieza en una celda no depende de cómo hayas llegado allí. Es 1 más el camino más largo desde el mejor de sus vecinos de mayor valor.
Calcula ese número una vez por celda y guárdalo. Puedes rellenarlo mediante una búsqueda en profundidad sobre vecinos más grandes, controlada por tu propia pila, o pelar la cuadrícula desde sus picos, una capa a la vez, y contar las capas.
Solución
Dibuja una flecha desde cada celda hacia cada vecino más grande. Los valores aumentan a lo largo de cada flecha, así que ninguna cadena de flechas puede formar un ciclo: la cuadrícula es un grafo dirigido acíclico, y la respuesta es su camino más largo. Sin ciclos, el camino más largo desde una celda depende únicamente de esa celda, así que lo calculas una vez por celda: O(m × n).
Sigue cada camino ascendente
Correcto, pero no termina con las pruebas más grandes
Intuición
Inicia un recorrido en cada celda y sigue cada rama hacia vecinos mayores hasta que no quede ninguna; el recorrido más largo es la respuesta. Los valores aumentan en cada paso, así que un recorrido nunca vuelve a una celda y no necesita un conjunto de visitados.
El recorrido desde una celda se repite cada vez que otro recorrido pasa por ella. En una cuadrícula de 100 × 100 donde cada valor es la suma de su fila y su columna, cada paso a la derecha o hacia abajo sube, y más de 10^58 recorridos salen de la esquina superior izquierda.
Algoritmo
- Para cada celda, apila (esa celda, 1) en una pila.
- Desapila una entrada (celda, longitud) y actualiza la respuesta con longitud.
- Apila (vecina, longitud + 1) por cada vecina dentro de la cuadrícula cuyo valor sea estrictamente mayor.
- Repite hasta que la pila esté vacía y después pasa a la siguiente celda inicial.
- Devuelve la mayor longitud encontrada.
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 answerBúsqueda en profundidad con memorización y tu propia pila
Intuición
Sea best[cell] el número de celdas en el camino creciente más largo que empieza ahí: 1 + max(best[nb]) entre los vecinos mayores nb, o 1 si no hay ninguno. Es seguro almacenarlo porque las celdas anteriores a cell en un camino son todas más pequeñas y nunca aparecen después de ella. En el primer ejemplo, 9 obtiene 1, 8 obtiene 2, 7 obtiene 3, 6 y 2 obtienen 4, 5 y 1 obtienen 5, 4 obtiene 6 y 3 obtiene 7.
Un camino también puede pasar por las 10,000 celdas, lo que es demasiado profundo para la recursión, así que usa tu propia pila. La celda de la cima prueba su siguiente dirección y apila un vecino mayor que no esté terminado. Una vez probadas las cuatro direcciones, se extrae la celda de la pila y se establece su best. No hace falta una marca de «en progreso»: cada celda de la pila es mayor que la que está debajo.
Algoritmo
- Rellena
bestcon 0 (aún no se conoce) y establece en 0 un contador de direcciones para cada celda. - Para cada celda cuyo
bestsea 0, añádela a una pila. - En la celda que está en la cima, avanza su contador y añade ese vecino a la pila si está dentro de la cuadrícula, es mayor y no ha terminado.
- Después de cuatro direcciones, extrae la celda y establece
besten 1 más elbestmás grande entre sus vecinos mayores, o en 1. - Devuelve el
bestmás grande.
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 answerDespega la cuadrícula desde sus picos
Intuición
Construye la misma tabla desde los valores más altos hacia abajo, como en la ordenación topológica de Kahn. Un pico, una celda sin vecinos mayores, inicia un camino de 1 celda: capa 1. Elimina todos los picos; las celdas que se quedaron sin ningún vecino mayor pasan a ser la siguiente capa. Repite hasta que la cuadrícula esté vacía. Una celda va una ronda después de su último vecino mayor, así que su capa es igual a su best, y el número de capas es la respuesta. En el primer ejemplo, las capas son 9; 8; 7; 2 y 6; 1 y 5; 4; 3.
Cuenta cuántos vecinos mayores quedan para cada celda. Al eliminar una celda, se reduce el contador de cada vecino estrictamente menor, y un contador de 0 la coloca en la siguiente capa. Cada celda se elimina una vez: O(m × n), sin usar una pila.
Algoritmo
- Para cada celda, cuenta los vecinos con un valor mayor.
- Coloca en la capa actual todas las celdas cuyo recuento sea 0.
- Mientras la capa no esté vacía, suma 1 al recuento de capas. Para cada celda que contiene, reduce el recuento de cada vecino estrictamente menor y coloca en la capa siguiente cualquier vecino cuyo recuento llegue a 0.
- Haz que la capa siguiente sea la actual y repite.
- Devuelve el recuento de capas.
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
Errores comunes y casos límite
- Comparar con
>=en lugar de>. Con dos 4 contiguos, una búsqueda por fuerza bruta va y viene para siempre, y una búsqueda con memoización lee una longitud que todavía se está calculando. - Usar recursión en Python. Los valores que serpentean por una cuadrícula de 100 × 100 forman un camino de 10,000 celdas, diez veces el límite predeterminado de 1,000 llamadas.
- Omitir las celdas terminadas como haría un rellenado por inundación. Su longitud almacenada es exactamente lo que necesita la celda actual.
- Empezar solo por el valor más pequeño. En el primer ejemplo, el 1 da 5 celdas, pero la respuesta, 7, empieza en el 3.
- Empezar las longitudes en 0. Una cuadrícula de valores iguales tiene como respuesta 1.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de la ruta creciente más larga en una matriz?
Tiempo y espacio O(m × n), con una búsqueda en profundidad con memorización o mediante eliminación progresiva: cada celda se procesa una vez y examina sus 4 vecinos. Probar todos los caminos desde cada celda es exponencial.
¿El problema de la ruta creciente más larga en una matriz es un problema de programación dinámica o de grafos?
Ambas cosas. Es el camino más largo en un grafo acíclico dirigido, lo que corresponde a programación dinámica sobre un orden topológico. Ordenar las celdas de mayor a menor valor da otro orden válido, a costa de O(m × n × log(m × n)) para la ordenación.
¿En qué se diferencia esto de la subsecuencia creciente más larga?
Una subsecuencia puede omitir elementos, pero conserva su orden; aquí, un camino debe avanzar a una celda contigua, en cualquiera de las cuatro direcciones. En ambos casos, una cadena estrictamente creciente nunca puede volver sobre sí misma.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def longestIncreasingPath(matrix):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Salida Esperada
7