Longest Increasing Path in a Matrix
Você recebe matrix, uma grade de números inteiros com m linhas e n colunas, como uma lista de linhas. Um caminho avança para cima, para baixo, para a esquerda ou para a direita (sem diagonais nem voltas pelas bordas), e cada passo deve chegar a um valor estritamente maior. Retorne o número de células no caminho mais longo desse tipo. Uma única célula forma um caminho de 1 célula.
Função
- matrixinteger-2d-array
- a grade de valores, como uma lista de linhas de mesmo comprimento
- Retornainteger
- o número de células no caminho estritamente crescente mais longo
Restrições
1 ≤ m, n ≤ 100, em quem = matrix.lengthen = matrix[i].length- Cada linha tem o mesmo comprimento
n. 0 ≤ matrix[i][j] ≤ 231-1
Exemplos
- Entrada
- matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
- Saída
- 7
- Explicação
- O caminho 3, 4, 5, 6, 7, 8, 9 desce pela coluna da direita, segue pela linha de baixo e sobe pela coluna do meio até o 9: 7 células. A partir do menor valor, 1, os melhores caminhos têm 5 células.
- Entrada
- matrix = [[2, 2, 2], [2, 5, 2]]
- Saída
- 2
- Explicação
- Valores iguais não representam um passo para cima, então nenhum caminho percorre os 2s. O melhor é dar um passo de um dos três 2s ao redor do 5 até o 5: 2 células.
- Entrada
- matrix = [[4, 4], [4, 4], [4, 4]]
- Saída
- 1
- Explicação
- Todos os valores são 4, então nenhuma etapa é permitida em lugar algum. Cada célula, sozinha, é um caminho de 1 célula, e 1 é a resposta.
Para ir além
Você também pode retornar as células de um dos caminhos mais longos, junto com seu comprimento?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Um caminho pode voltar a uma célula que já visitou? Observe o que os valores fazem ao longo do caminho.
Os valores só aumentam, então um caminho nunca repete uma célula, e o caminho mais longo que começa em uma célula não depende de como você chegou até ela. Ele é igual a 1 mais o caminho mais longo a partir do melhor de seus vizinhos com valores maiores.
Calcule esse número uma vez por célula e armazene-o. Você pode preenchê-lo com uma busca em profundidade sobre os vizinhos maiores, controlada pela sua própria pilha, ou descascar a grade a partir dos seus picos, uma camada de cada vez, e contar as camadas.
Solução
Desenhe uma seta de cada célula para cada vizinho maior. Os valores aumentam ao longo de cada seta, então nenhuma cadeia de setas pode formar um ciclo: a grade é um grafo acíclico direcionado, e a resposta é seu caminho mais longo. Sem ciclos, o caminho mais longo a partir de uma célula depende apenas dessa célula, então você o calcula uma vez por célula: O(m × n).
Siga todos os caminhos crescentes
Correta, mas não termina nos maiores testes
Intuição
Inicie uma caminhada em cada célula e siga cada ramificação de vizinhos maiores até não restar nenhum; a caminhada mais longa é a resposta. Os valores aumentam a cada passo, então uma caminhada nunca retorna a uma célula e não precisa de um conjunto de visitados.
A caminhada a partir de uma célula é refeita toda vez que outra caminhada passa por ela. Em uma grade de 100 × 100 em que cada valor é a soma da linha com a coluna, cada passo para a direita ou para baixo sobe, e mais de 10^58 caminhadas partem do canto superior esquerdo.
Algoritmo
- Para cada célula, coloque (essa célula, 1) em uma pilha.
- Remova uma entrada (célula, comprimento) e atualize a resposta com o comprimento.
- Coloque (vizinho, comprimento + 1) para cada vizinho dentro da grade com um valor estritamente maior.
- Repita até que a pilha esteja vazia e, em seguida, passe para a próxima célula inicial.
- Retorne o maior comprimento encontrado.
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 answerBusca em profundidade com memorização usando sua própria pilha
Intuição
Seja best[cell] o número de células no caminho crescente mais longo que começa ali: 1 + max(best[nb]) entre os vizinhos maiores nb, ou 1 se não houver nenhum. É seguro armazenar esse valor porque as células anteriores a cell em um caminho são todas menores e nunca vêm depois dela. No primeiro exemplo, 9 recebe 1, 8 recebe 2, 7 recebe 3, 6 e 2 recebem 4, 5 e 1 recebem 5, 4 recebe 6, e 3 recebe 7.
Um caminho também pode passar pelas 10.000 células, profundidade demais para a recursão, então use sua própria pilha. A célula no topo tenta a próxima direção e empilha um vizinho maior que ainda não foi concluído. Depois que as quatro direções forem tentadas, remova a célula da pilha e defina seu best. Não é necessário marcar como "em andamento": cada célula na pilha é maior que a célula abaixo dela.
Algoritmo
- Preencha
bestcom 0 (ainda não conhecido) e um contador de direções com 0 para cada célula. - Para cada célula com
bestigual a 0, coloque-a em uma pilha. - Na célula do topo, avance seu contador e coloque aquele vizinho na pilha se estiver dentro da grade, for maior e não estiver concluído.
- Após quatro direções, retire a célula da pilha e defina
bestcomo 1 mais o maiorbestentre seus vizinhos maiores, ou 1. - Retorne o maior
best.
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 answerRemova a grade de seus picos
Intuição
Construa a mesma tabela começando pelos valores mais altos, como na ordenação topológica de Kahn. Um pico, uma célula sem vizinhos maiores, inicia um caminho de 1 célula: camada 1. Remova todos os picos; as células que perderam seu último vizinho maior formam a próxima camada. Repita até que a grade fique vazia. Uma célula entra uma rodada depois de seu último vizinho maior, então sua camada é igual a best, e o número de camadas é a resposta. No primeiro exemplo, as camadas são 9; 8; 7; 2 e 6; 1 e 5; 4; 3.
Conte quantos vizinhos maiores restam para cada célula. Remover uma célula diminui a contagem de cada vizinho estritamente menor, e uma contagem de 0 coloca a célula na próxima camada. Cada célula é removida uma vez: O(m × n), sem pilha.
Algoritmo
- Para cada célula, conte os vizinhos com um valor maior.
- Coloque na camada atual cada célula cuja contagem seja 0.
- Enquanto a camada não estiver vazia, adicione 1 à contagem de camadas. Para cada célula nela, diminua a contagem de cada vizinho estritamente menor e coloque na próxima camada qualquer vizinho cuja contagem chegue a 0.
- Faça da próxima camada a camada atual e repita.
- Retorne a contagem de camadas.
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
Armadilhas e casos extremos
- Comparar usando
>=em vez de>. Com dois 4s vizinhos, uma busca por força bruta fica indo e voltando para sempre, e uma busca com memoização lê um comprimento que ainda está sendo calculado. - Usar recursão em Python. Valores que serpenteiam por uma grade de 100 × 100 formam um caminho de 10.000 células, dez vezes o limite padrão de 1.000 chamadas.
- Pular as células concluídas, como faria uma busca em largura. O comprimento armazenado nelas é exatamente o que a célula atual precisa.
- Começar apenas pelo menor valor. No primeiro exemplo, o 1 resulta em 5 células, mas a resposta, 7, começa no 3.
- Começar os comprimentos em 0. Uma grade com valores iguais tem resposta 1.
Perguntas frequentes3
Qual é a complexidade de tempo do caminho crescente mais longo em uma matriz?
Tempo e espaço O(m × n), com busca em profundidade com memoização ou com remoção de camadas: cada célula é finalizada uma vez e verifica seus 4 vizinhos. Tentar todos os caminhos a partir de cada célula tem complexidade exponencial.
O Caminho Crescente Mais Longo em uma Matriz é um problema de programação dinâmica ou de grafos?
Ambos. É o caminho mais longo em um grafo acíclico direcionado, o que envolve programação dinâmica sobre uma ordenação topológica. Ordenar as células do maior para o menor valor fornece outra ordem válida, ao custo de O(m × n × log(m × n)) para a ordenação.
Qual é a diferença entre isso e a subsequência crescente mais longa?
Uma subsequência pode pular elementos, mas mantém a ordem deles; aqui, um caminho deve avançar para uma célula adjacente, em qualquer uma das quatro direções. Em ambos os casos, uma sequência estritamente crescente nunca pode voltar sobre si mesma.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def longestIncreasingPath(matrix):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Saída Esperada
7