Longest Increasing Path in a Matrix

DifícilProgramação dinâmica Grafos Ordenação topológica

+10

Você recebe matrix, uma grade de números inteiros com m linhas e n colunas, como uma lista de linhas. Um caminho se move de uma célula para outra, um passo para cima, para baixo, para a esquerda ou para a direita de cada vez (sem passos diagonais e sem passar de uma borda para a outra), 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, por si só, é um caminho de 1 célula.

Função

longestIncreasingPath(matrix: integer-2d-array) → integer

matrixinteger-2d-array: a grade de valores, como uma lista de linhas de comprimento igual
Retornainteger: o número de células no caminho estritamente crescente mais longo

Restrições

1 ≤ m, n ≤ 100, onde m = matrix.length e n = matrix[i].length
Cada linha tem o mesmo comprimento n.
0 ≤ matrix[i][j] ≤ 2³¹-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 para a esquerda pela linha inferior, sobe pela coluna do meio e vai para a esquerda até o 9 no canto: 7 células. O menor valor tem um resultado pior: a partir do 1, os melhores caminhos são 1, 2, 7, 8, 9 e 1, 6, 7, 8, 9, com 5 células cada.

+18 testes ocultos ao enviar

Para ir além

Você também pode retornar as células de um dos caminhos mais longos, e não apenas seu comprimento?

Solução

Desenhe uma seta de cada célula para cada vizinha que contenha um valor maior. Os valores aumentam ao longo de cada seta, então nenhuma cadeia de setas pode voltar ao ponto de partida: a grade é um grafo acíclico direcionado, e a tarefa consiste em encontrar seu caminho mais longo. Em um grafo geral, essa questão é inviável para entradas grandes, mas, sem ciclos, o caminho mais longo a partir de uma célula depende apenas dela; assim, você o calcula uma vez por célula, e o problema inteiro cai para O(m × n). Uma busca em profundidade com memoização o calcula de cima para baixo; removendo as células da grade a partir dos picos, o algoritmo de Kahn em ordem inversa o calcula de baixo para cima.

Siga cada caminho crescente

Correta, mas não termina nos maiores testes

Intuição

Comece uma caminhada em cada célula. A partir da célula em que você está, tente cada um dos quatro vizinhos cujo valor seja maior e, a partir daí, continue da mesma maneira até que não reste nenhum vizinho com valor maior. Conte as células de cada caminhada e mantenha a maior contagem.

A caminhada não precisa de um conjunto de visitados. Os valores aumentam a cada passo, então a caminhada nunca pode voltar a uma célula: para chegar a ela novamente, teria que voltar ao valor daquela célula. Mantenha as caminhadas em uma pilha de entradas (célula, comprimento). Remover uma entrada da pilha encerra uma caminhada naquela célula, e adicionar seus vizinhos com valores maiores a estende.

O método está correto e é desesperadoramente lento, porque as caminhadas se ramificam. Em uma grade de 100 × 100 em que cada valor é a soma de sua linha e sua coluna, cada passo para a direita ou para baixo é um passo para cima, e as caminhadas que partem apenas do canto superior esquerdo são mais de 10^58. Pior ainda: a caminhada a partir de qualquer célula é refeita toda vez que outra caminhada passa por ela, desperdício que a próxima abordagem elimina.

Algoritmo

Para cada célula, empilhe (essa célula, 1) em uma pilha.
Retire uma entrada (célula, comprimento) e atualize a resposta com o comprimento.
Empilhe (vizinha, comprimento + 1) para cada vizinha 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 answer

Busca em profundidade memoizada com sua própria pilha

Intuição

Seja best[cell] o número de células no caminho crescente mais longo que começa nessa célula. O caminho termina ali mesmo ou seu próximo passo vai para um vizinho maior e continua pelo caminho mais longo a partir desse vizinho. Portanto, best[cell] = 1 + max(best[nb]) entre os vizinhos maiores nb, ou 1 se não houver nenhum. É seguro reutilizar esse resultado por causa da estrutura acíclica: as células anteriores a cell em qualquer caminho são todas menores, então nunca podem aparecer depois dela, e a melhor continuação a partir de cell é a mesma, independentemente de como você chegou até ela. Calcule cada best uma vez, armazene-o, e a árvore exponencial de percursos se reduz a uma visita por célula.

No primeiro exemplo, 9 não tem nenhum vizinho maior, então best é 1 ali. Depois, 8 recebe 2, 7 recebe 3, 6 e 2 recebem 4, 5 e 1 recebem 5, 4 recebe 6, e 3 recebe 7, que é a resposta. Cada célula verifica seus 4 vizinhos, então o trabalho é O(m × n).

O código natural é recursivo: uma função que retorna best para uma célula, chamando a si mesma para cada vizinho maior. A profundidade das chamadas é igual ao comprimento do caminho que ela percorre, e as restrições permitem um caminho que passa por todas as células: valores que serpenteiam para frente e para trás em uma grade de 100 × 100 formam um caminho de 10.000 células, enquanto o Python para por padrão em 1.000 chamadas aninhadas. O código abaixo executa a própria recursão, então nenhum caminho é longo demais para ele. Mantenha uma pilha de células e, para cada célula, quantas das quatro direções você já tentou. Observe a célula no topo: se ainda houver uma direção, tente-a e empilhe o vizinho nessa direção quando ele for maior e ainda não tiver sido concluído. Quando as quatro direções tiverem sido tentadas, todos os vizinhos maiores estarão concluídos, então retire a célula da pilha e defina seu best. Essa é exatamente a ordem que uma chamada recursiva seguiria.

A busca não precisa de uma marcação de "em andamento", ao contrário da detecção de ciclos. Cada célula na pilha é maior que a célula abaixo dela, então um vizinho maior da célula no topo nunca pode estar mais abaixo na pilha.

Algoritmo

Preencha best com 0 (ainda desconhecido) e um contador de direções com 0 para cada célula.
Para cada célula com best igual a 0, coloque-a em uma pilha.
Observe a célula no topo. Se ainda houver uma direção disponível, avance seu contador e coloque na pilha a célula vizinha nessa direção, se ela estiver dentro da grade, for maior e não estiver concluída.
Se as quatro direções já tiverem sido tentadas, retire a célula da pilha e defina best como 1 mais o maior best entre suas células vizinhas maiores, ou como 1 se não houver nenhuma.
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 answer

Descasque a grade a partir de seus picos

Intuição

Inverta a programação dinâmica e construa a resposta dos maiores valores para os menores, da mesma forma que o algoritmo de Kahn constrói uma ordenação topológica. Chame uma célula de pico quando nenhum vizinho é maior. Um caminho a partir de um pico não pode avançar, então tem 1 célula. Remova todos os picos de uma vez: essa é a camada 1. Agora algumas células perderam seu último vizinho maior, então são picos do que restou. Remova-as como camada 2 e continue até que a grade fique vazia. O número de camadas é a resposta.

Por quê: uma célula fica na camada k exatamente quando o caminho mais longo que começa nela tem k células. Uma célula é removida na rodada depois que seu último vizinho maior é removido, então sua camada é 1 mais a camada mais alta entre seus vizinhos maiores, que é a fórmula best[cell] = 1 + max(best[nb]) da abordagem anterior. A camada mais profunda pertence ao início de um caminho mais longo.

No primeiro exemplo, o único pico é o 9 (seus vizinhos são 8 e 2). Removê-lo libera o 8; remover o 8 libera o 7; remover o 7 libera o 2 e o 6; esses dois liberam o 1 e o 5; o 5 libera o 4; e o 4 libera o 3. São 7 camadas, e o caminho 3, 4, 5, 6, 7, 8, 9 sobe passando por uma célula de cada camada.

Para encontrar rapidamente a próxima camada, conte quantos vizinhos maiores cada célula ainda tem. Remover uma célula diminui a contagem de cada vizinho estritamente menor, e uma contagem que chega a 0 coloca esse vizinho na próxima camada. Cada célula é removida uma vez e cada par de vizinhos é examinado um número constante de vezes, então o trabalho é O(m × n), sem pilha e sem recursão.

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 o vizinho cuja contagem chegar 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

Os bugs aqui vêm da palavra "estritamente", da recursão profunda e de hábitos trazidos de outros problemas de grade.

Comparar com >= em vez de >. Com dois 4s vizinhos, cada um conta como um passo acima do outro, as setas formam um ciclo, uma busca por força bruta vai e volta para sempre, e uma busca com memoização lê um comprimento que ainda está sendo calculado.
Recursão em caminhos muito longos. Uma busca recursiva faz tantas chamadas em profundidade quanto o caminho é longo, e as restrições permitem um caminho que passa por todas as células: valores que serpenteiam para frente e para trás em uma grade de 100 × 100 formam um caminho de 10,000 células, dez vezes o limite padrão do Python de 1,000 chamadas aninhadas. Caminhos tão longos exigem uma busca iterativa com sua própria pilha, ou um limite de recursão aumentado (sys.setrecursionlimit em Python), e um limite muito alto ainda pode exceder a própria pilha do interpretador.
Pular células já visitadas, como faz um preenchimento por inundação. Chegar a uma célula já concluída não é um beco sem saída: o comprimento armazenado nela é exatamente o que a célula atual precisa. Leia esse valor, não pule a célula.
Começar apenas pelo menor valor. No primeiro exemplo, o 1 dá 5 células, mas a resposta, 7, começa no 3. O caminho mais longo pode começar em qualquer célula que não tenha um vizinho menor, e pode haver muitas células assim.
Retornar 0. Cada célula é um caminho de 1 célula, então uma grade de valores iguais, ou uma grade de 1 × 1, tem resposta 1. Comece o comprimento de cada célula em 1, não em 0.
Na abordagem de remoção em camadas, diminuir a contagem de um vizinho igual. Apenas um vizinho estritamente menor perdeu um vizinho maior.

Perguntas frequentes4

Qual é a complexidade de tempo do Longest Increasing Path in a Matrix?

Tempo O(m × n) e espaço O(m × n) com busca em profundidade memorizada ou com remoção topológica. Cada uma das m × n células é finalizada uma vez e verifica seus 4 vizinhos um número constante de vezes, e cada método mantém um número por célula. Tentar todos os caminhos a partir de cada célula é exponencial: em uma grade de 100 × 100 em que cada valor é a soma de sua linha e coluna, mais de 10^58 caminhos saem do canto superior esquerdo.

Por que esse problema não precisa de um conjunto de visitados?

Um caminho que só sobe nunca pode retornar a uma célula, porque teria que voltar para o valor daquela célula. Portanto, a regra de crescimento estrito já impede revisitas, e o grafo de passos não tem ciclos. É também por isso que a memoização é segura: as células anteriores a uma determinada célula não podem interferir no caminho depois dela.

O problema do caminho mais longo crescente em uma matriz é de programação dinâmica ou de grafos?

Ambos. É o caminho mais longo em um grafo acíclico direcionado, o que corresponde à programação dinâmica em uma ordem topológica: a resposta de uma célula é 1 mais a melhor resposta entre suas vizinhas maiores. A busca em profundidade com memoização preenche a tabela na ordem em que a busca termina de processar as células, e a remoção topológica preenche a tabela camada por camada, começando pelos picos. Ordenar as células do maior valor para o menor fornece uma terceira ordem válida, ao custo de O(m × n × log(m × n)) para a ordenação.

Em que isso difere da subsequência crescente mais longa?

Uma subsequência pode pular elementos e deve manter a ordem deles, enquanto um caminho aqui deve avançar para uma célula adjacente, em qualquer uma das quatro direções. O problema da subsequência é de programação dinâmica em uma linha; este é de programação dinâmica em uma grade transformada em um grafo. Ambos se baseiam no mesmo fato: uma cadeia estritamente crescente nunca pode voltar sobre si mesma.

Python

def longestIncreasingPath(matrix):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]

Esperado

Longest Increasing Path in a Matrix

Função

Restrições

Exemplos

Dicas

Solução

Siga cada caminho crescente

Busca em profundidade memoizada com sua própria pilha

Descasque a grade a partir de seus picos

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos