Container With Most Water

Q: Qual é a complexidade de tempo do problema Container With Most Water?

A solução com dois ponteiros é executada em O(n) tempo e O(1) de espaço extra, já que cada etapa move um ponteiro uma posição para dentro. Verificar cada par leva O(n²), e ordenar as linhas por altura leva O(n log n).

Q: Por que mover o ponteiro para a linha mais curta?

A água é limitada pela linha mais curta. Qualquer outro recipiente que mantenha essa linha tem uma parceira mais próxima, então é mais estreito e não é mais alto. Nenhum deles consegue superar o recipiente que você mediu, então a linha mais curta pode ser descartada sem perder a resposta.

Q: Container With Most Water é um problema guloso?

Sim. Cada etapa faz uma escolha local que nunca é desfeita: descartar a linha mais curta. A escolha é segura porque qualquer recipiente descartado por ela não é melhor do que um já medido, e é por isso que o problema se enquadra tanto em algoritmos gulosos quanto em dois ponteiros.

MédioDois ponteiros Guloso

+10

Você recebe uma lista height de números inteiros não negativos. A linha i é uma parede vertical de altura height[i] na posição i. Quaisquer duas linhas formam um recipiente com o chão, que comporta uma quantidade de água igual à altura da linha mais baixa multiplicada pela distância entre as duas linhas. As outras linhas não atrapalham. Retorne a maior quantidade de água que um único par de linhas pode comportar.

Função

maxArea(height: integer-array) → integer

heightinteger-array: as alturas das linhas nas posições 0, 1, 2 e assim por diante
Retornainteger: a maior quantidade de água que duas linhas podem conter

Restrições

2 ≤ height.length ≤ 10⁴
0 ≤ height[i] ≤ 10⁴
A resposta é no máximo 10⁸, então cabe em um inteiro de 32 bits.

Exemplos

Entrada: height = [3, 7, 2, 5, 4, 7, 3, 6]
Saída: 36
Explicação: As linhas nas posições 1 e 7, com alturas 7 e 6, estão separadas por 6 e comportam 6 × 6 = 36. As duas linhas mais altas, os 7 nas posições 1 e 5, comportam apenas 7 × 4 = 28.

Para ir além

Aqui, as linhas entre as duas são ignoradas. Se cada linha fosse uma barra sólida, quanta água se acumularia entre todas elas? Você também consegue calcular isso em O(n)?

Solução

Verificar todos os n²/2 pares significa calcular 5 × 10^7 produtos para 10^4 linhas. A quantidade de água depende apenas da linha mais curta de um par, então, quando uma linha é o lado mais curto do recipiente mais largo que ela ainda pode formar, nenhum recipiente mais estreito que a use pode ser melhor. Dois ponteiros transformam isso em uma única passagem a partir das duas extremidades.

Verifique cada par

Correta, mas não termina nos maiores testes

Intuição

Um par i < j corresponde a min(height[i], height[j]) × (j - i): a água transborda pela parede mais baixa, e o fundo tem j - i de largura. Teste todos os pares e mantenha o maior valor.

n linhas geram n(n-1)/2 pares: cerca de 5 × 10^7 para 10^4 linhas, e quatro vezes mais a cada vez que n dobra.

Algoritmo

Defina best como 0.
Para cada i e cada j depois dele, calcule min(height[i], height[j]) × (j - i).
Mantenha o maior entre best e esse valor.
Retorne best.

def maxArea(height):
    n = len(height)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            best = max(best, water)
    return best

As linhas mais altas primeiro

Intuição

Se a linha i for o lado mais curto de um recipiente, sua parceira poderá ser qualquer linha pelo menos tão alta quanto ela. Portanto, o melhor recipiente desse tipo combina essa linha com a linha mais distante que seja pelo menos tão alta.

Ordene as linhas da mais alta para a mais baixa. Quando chega a vez da linha i, todas as linhas já posicionadas são pelo menos tão altas, e a mais distante é o índice posicionado mais à esquerda ou mais à direita, lo ou hi. Portanto, a linha i comporta, no máximo, height[i] × max(i - lo, hi - i), e o melhor recipiente é contabilizado quando sua linha mais baixa chega. Entre duas linhas de mesma altura, a segunda a ser posicionada vê a primeira como parceira.

No primeiro exemplo, os valores 7 nas posições 1 e 5 vêm primeiro e comportam 28. O valor 6 na posição 7 então vê lo = 1 e comporta 36. A ordenação custa O(n log n) de tempo e O(n) de memória.

Algoritmo

Ordene os índices por altura, do mais alto para o mais baixo.
Defina lo e hi como o primeiro índice dessa ordem e best como 0.
Para cada próximo índice i, calcule height[i] vezes o maior valor entre i - lo e hi - i, e mantenha o melhor valor.
Atualize lo e hi para incluir i.
Retorne best.

def maxArea(height):
    # Indices from the tallest line to the shortest.
    order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
    lo = hi = order[0]  # leftmost and rightmost index among the lines placed so far
    best = 0
    for i in order[1:]:
        # Every placed line is at least as tall as line i, so line i is the
        # shorter side, and its best partner is the placed line farthest away.
        best = max(best, height[i] * max(i - lo, hi - i))
        lo = min(lo, i)
        hi = max(hi, i)
    return best

Dois ponteiros, um em cada extremidade

Intuição

Comece com o recipiente mais largo, left = 0 e right = n-1, e considere que height[left] ≤ height[right]. Qualquer outro recipiente que use a linha left a combina com uma linha mais próxima, então ele é mais estreito e não é mais alto que height[left]. Nenhum deles comporta mais água do que a que você mediu, então a linha left está resolvida e left avança um passo para a direita. Se as alturas forem iguais, ambas as linhas estão resolvidas, então mover qualquer uma delas está correto.

A cada passo, uma linha é descartada, então os ponteiros se encontram após n-1 passos. O melhor par nunca é ignorado: quando a primeira de suas duas linhas é descartada, o recipiente medido naquele momento comporta pelo menos a mesma quantidade.

No primeiro exemplo, as posições 0 e 7 comportam 21, e o 3 é descartado. As posições 1 e 7 comportam 36, e o 6 é descartado. Os demais comportam 15, 28, 12, 10 e 2.

Algoritmo

Defina left = 0, right = n-1 e best = 0.
Enquanto left < right, calcule min(height[left], height[right]) × (right - left) e mantenha o melhor valor.
Se height[left] < height[right], mova left um passo para a direita. Caso contrário, mova right um passo para a esquerda.
Quando os ponteiros se encontrarem, retorne best.

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        best = max(best, water)
        # The shorter line cannot do better with any line closer in, so drop it.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

Armadilhas e casos extremos

Mover a linha mais alta. No primeiro exemplo, que retorna 21 em vez de 36: o 6 na posição 7 sai antes mesmo de encontrar o 7 na posição 1.
Usar a linha mais alta, ou a média das duas, como altura. A água transborda pela parede mais baixa, então a altura é o mínimo.
Medir a largura como j - i + 1. As linhas nas posições i e j estão separadas por j - i, então [4, 4] comporta 4, não 8.
Supor que a resposta usa as linhas mais altas ou o par das extremidades. No primeiro exemplo, os dois 7s comportam 28 e o par das extremidades, 21, enquanto a resposta é 36.

Perguntas frequentes3

Qual é a complexidade de tempo do problema Container With Most Water?

A solução com dois ponteiros é executada em O(n) tempo e O(1) de espaço extra, já que cada etapa move um ponteiro uma posição para dentro. Verificar cada par leva O(n²), e ordenar as linhas por altura leva O(n log n).

Por que mover o ponteiro para a linha mais curta?

A água é limitada pela linha mais curta. Qualquer outro recipiente que mantenha essa linha tem uma parceira mais próxima, então é mais estreito e não é mais alto. Nenhum deles consegue superar o recipiente que você mediu, então a linha mais curta pode ser descartada sem perder a resposta.

Container With Most Water é um problema guloso?

Sim. Cada etapa faz uma escolha local que nunca é desfeita: descartar a linha mais curta. A escolha é segura porque qualquer recipiente descartado por ela não é melhor do que um já medido, e é por isso que o problema se enquadra tanto em algoritmos gulosos quanto em dois ponteiros.

def maxArea(height):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

height = [3, 7, 2, 5, 4, 7, 3, 6]

Saída Esperada

Container With Most Water

Função

Restrições

Exemplos

Dicas

Solução

Verifique cada par

As linhas mais altas primeiro

Dois ponteiros, um em cada extremidade

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos