Container With Most Water

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

A solução com dois ponteiros é executada em O(n) de tempo e usa O(1) de espaço extra. A cada etapa, um ponteiro se move uma posição para dentro, portanto há no máximo n-1 etapas. Verificar cada par leva O(n²), e ordenar as linhas por altura leva O(n log n).

Q: Por que mover o ponteiro na 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 ainda não é mais alto que a linha mais curta. Nenhum deles pode superar o recipiente que você mediu, então a linha mais curta pode ser descartada sem perder a resposta.

Q: O problema Container With Most Water é um problema guloso?

Sim. Cada etapa faz uma escolha local que nunca é desfeita, descartando a linha mais curta. A escolha é segura porque todo recipiente descartado pela etapa não é melhor do que um já medido. É por isso que o problema é classificado tanto como guloso quanto como de dois ponteiros.

Q: Qual é a diferença entre Container With Most Water e Trapping Rain Water?

Aqui, apenas as duas linhas escolhidas importam, e as linhas entre elas são ignoradas, então a resposta é um único retângulo. Em Trapping Rain Water, cada barra é sólida, e a água se acumula acima de cada barra até a altura da menor das barras mais altas em seus dois lados, então a resposta é uma soma sobre todas as posições. Ambos têm soluções O(n) com dois ponteiros, mas as regras para os ponteiros e o que você soma são diferentes.

MédioDois ponteiros Guloso

+10

Você recebe uma lista height de inteiros não negativos. A linha i é uma parede vertical de altura height[i], posicionada em 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 conter.

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 têm alturas 7 e 6 e estão separadas por 6, então comportam 6 × 6 = 36. As duas linhas mais altas, os 7 nas posições 1 e 5, comportam apenas 7 × 4 = 28, e o par externo comporta 3 × 7 = 21.

+15 testes ocultos ao enviar

Para ir além

Aqui, as linhas entre as duas que você escolher 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

Há cerca de n²/2 pares de linhas, então, para 10^4 linhas, verificar todos eles significa fazer 5 × 10^7 produtos. A solução é que a quantidade de água depende apenas da linha mais curta de um par: quando você sabe que uma linha é o lado mais curto do recipiente mais largo que ela ainda pode formar, nenhum recipiente mais estreito que a use consegue ser melhor. Dois ponteiros transformam esse fato em uma única passagem pelas duas extremidades.

Verifique cada par

Correta, mas não termina nos maiores testes

Intuição

Cada recipiente corresponde a um par de posições i < j. A água sobe até transbordar pela parede mais baixa, e o piso entre as paredes tem largura j - i, então o par comporta min(height[i], height[j]) × (j - i). Experimente todos os pares, mantenha o maior e, por definição, você terá a resposta.

O problema é a quantidade de pares. 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 a lista dobra de tamanho. Uma linguagem compilada dá conta disso em uma fração de segundo, mas Python, Ruby ou R precisam de muitos segundos, e a contagem cresce rápido demais para qualquer linguagem quando n chega a 10^5.

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

Linhas mais altas primeiro

Intuição

Observe um recipiente pelo lado de sua linha mais curta. Se a linha i for o lado mais curto, a quantidade de água será height[i] vezes a distância, e a linha parceira poderá ser qualquer linha pelo menos tão alta. Portanto, o melhor recipiente em que i é o lado mais curto combina essa linha com a linha mais distante que seja pelo menos tão alta.

Para encontrar essas linhas parceiras rapidamente, ordene as linhas da mais alta para a mais baixa. Quando chega a vez da linha i, todas as linhas ordenadas antes dela têm altura pelo menos igual à dela, e a mais distante entre elas está no índice ordenado mais à esquerda ou mais à direita. Acompanhe esses dois índices, lo e hi, e a linha i comporta, no máximo, height[i] × max(i - lo, hi - i). A resposta é o maior desses valores, pois o melhor recipiente é contabilizado quando chega a vez de sua linha mais curta.

No primeiro exemplo, os dois 7 nas posições 1 e 5 vêm primeiro e comportam 28. O 6 na posição 7 vem em seguida, com lo = 1 e hi = 5, e comporta 6 × 6 = 36. Nenhuma linha mais baixa supera esse valor. Linhas de mesma altura podem vir em qualquer ordem: a que vier em segundo lugar entre duas linhas iguais verá a primeira como uma parceira.

A ordenação custa O(n log n) e a varredura, O(n), o que é rápido o suficiente. Ainda assim, é preciso O(n) de memória para a ordenação, e a próxima abordagem elimina tanto a ordenação quanto o uso 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 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 das duas extremidades

Intuição

Comece com o recipiente mais largo, left = 0 e right = n-1, e meça-o. Agora, uma das duas linhas pode sair, e a escolha é obrigatória: descarte a mais baixa. Suponha que height[left] ≤ height[right]. Todos os outros recipientes que usam a linha left a combinam com uma linha mais próxima do que right, então são mais estreitos, e sua altura continua sendo, no máximo, height[left]. Nenhum deles supera a quantidade de água que você mediu, então a linha left está descartada e left avança uma posição à direita. Mover a linha mais alta em vez disso manteria o mesmo limite para a altura e perderia largura, então só poderia piorar. Quando as duas alturas são iguais, ambas as linhas estão descartadas, e mover qualquer uma delas serve.

A cada passo, uma linha é descartada definitivamente; assim, após n-1 passos, os ponteiros se encontram. O melhor par nunca é ignorado: na primeira vez que uma de suas duas linhas é descartada, o recipiente medido naquele momento comporta pelo menos a mesma quantidade de água.

Em [3, 7, 2, 5, 4, 7, 3, 6], as posições 0 e 7 comportam 3 × 7 = 21. A linha de altura 3 é a mais baixa, então left avança para 1. As posições 1 e 7 comportam 6 × 6 = 36, e agora a linha de altura 6 é a mais baixa, então right recua para 6. Os recipientes seguintes comportam 15, 28, 12, 10 e 2, então a resposta continua sendo 36.

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

O loop de dois ponteiros é curto, então os erros estão nos detalhes.

Mover a linha mais alta. No primeiro exemplo, isso retorna 21 em vez de 36: o 6 na posição 7 é a linha mais alta do primeiro par, então ela 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.
Um erro de um na largura. As linhas nas posições i e j ficam a j - i de distância, não j - i + 1, então duas vizinhas contêm a altura menor vezes 1.
Presumir que a resposta usa a linha mais alta ou o par das extremidades. No primeiro exemplo, os dois 7s contêm 28 e o par das extremidades, 21, enquanto a resposta é 36.
Overflow com limites maiores. Aqui, a água fica abaixo de 10^8, mas, com alturas e comprimentos próximos de 10^5, o produto ultrapassa 2^31 e precisa de um inteiro de 64 bits.

Perguntas frequentes4

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

A solução com dois ponteiros é executada em O(n) de tempo e usa O(1) de espaço extra. A cada etapa, um ponteiro se move uma posição para dentro, portanto há no máximo n-1 etapas. Verificar cada par leva O(n²), e ordenar as linhas por altura leva O(n log n).

Por que mover o ponteiro na 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 ainda não é mais alto que a linha mais curta. Nenhum deles pode superar o recipiente que você mediu, então a linha mais curta pode ser descartada sem perder a resposta.

O problema Container With Most Water é um problema guloso?

Sim. Cada etapa faz uma escolha local que nunca é desfeita, descartando a linha mais curta. A escolha é segura porque todo recipiente descartado pela etapa não é melhor do que um já medido. É por isso que o problema é classificado tanto como guloso quanto como de dois ponteiros.

Qual é a diferença entre Container With Most Water e Trapping Rain Water?

Aqui, apenas as duas linhas escolhidas importam, e as linhas entre elas são ignoradas, então a resposta é um único retângulo. Em Trapping Rain Water, cada barra é sólida, e a água se acumula acima de cada barra até a altura da menor das barras mais altas em seus dois lados, então a resposta é uma soma sobre todas as posições. Ambos têm soluções O(n) com dois ponteiros, mas as regras para os ponteiros e o que você soma são diferentes.

Python

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

Casos de teste

Caso 1

Caso 2

Entrada

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

Esperado

Container With Most Water

Função

Restrições

Exemplos

Dicas

Solução

Verifique cada par

Linhas mais altas primeiro

Dois ponteiros das duas extremidades

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos