Trapping Rain Water
Uma fileira de barras fica lado a lado, cada uma com uma unidade de largura: height[i] é a altura da barra i. Chove sobre a fileira, e a água se acumula nas depressões entre as barras. A água só fica acima de uma barra se houver uma barra mais alta em algum ponto à sua esquerda e outra em algum ponto à sua direita; além da primeira e da última barra, ela escorre.
Retorne o número total de quadrados unitários de água que a fileira comporta.
Função
- heightinteger-array
- a altura de cada barra, da esquerda para a direita
- Retornainteger
- o total de unidades de água retida
Restrições
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- Cada barra tem uma unidade de largura, e a água não fica além da primeira nem da última barra.
Exemplos
- Entrada
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- Saída
- 7
- Explicação
- Entre o 3 e o 5, a água sobe até o nível 3: ela retém 2 unidades sobre a barra de 1, 3 sobre a de 0 e 1 sobre a de 2. O 1 perto do final fica entre o 5 e um 2, então seu nível é 2 e ele retém 1 unidade. 2 + 3 + 1 + 1 = 7.
- Entrada
- height = [4, 1, 3, 0, 5]
- Saída
- 8
- Explicação
- A parede mais baixa é a 4 à esquerda, então toda a depressão se enche até o nível 4: 3 unidades sobre o 1, 1 sobre o 3 e 4 sobre o 0, o que dá 8. O 5 à direita não eleva o nível, porque a água transbordaria pelo 4 primeiro.
- Entrada
- height = [1, 2, 4, 2, 1]
- Saída
- 0
- Explicação
- As barras sobem até 4 e depois descem. Cada barra tem um lado sem nada mais alto além dela, então a água escorre e a resposta é 0.
+17 testes ocultos ao enviar
Para ir além
Suponha que as barras formem uma grade 2D de alturas e que a água possa escapar nas quatro direções. Como você contaria a água retida nesse caso?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Esqueça a linha inteira e observe uma barra. Até que altura a água pode ficar acima da barra
i, e quais barras determinam essa altura?O nível da água acima da barra
ié o menor de dois números: a barra mais alta do início atéie a barra mais alta deiaté o fim. A barrairetém esse nível menos sua própria altura. Ambos os máximos acumulados podem ser calculados em uma única passagem a partir de cada extremidade.Você só precisa do menor dos dois máximos. Coloque um ponteiro em cada extremidade e mantenha a barra mais alta que cada ponteiro já encontrou. O nível do ponteiro que estiver sobre a barra mais baixa é determinado pelo seu próprio máximo acumulado: some essa água e mova esse ponteiro para dentro. Pare quando os ponteiros se encontrarem.
Solução
A água acima de cada barra depende de barras que podem estar bem distantes, em ambos os lados, então observar apenas as vizinhas leva ao resultado errado. A solução é uma fórmula: o nível acima de uma barra é o menor entre a barra mais alta à sua esquerda e a barra mais alta à sua direita. Percorrer cada barra para encontrar esses dois máximos é lento; armazená-los em dois arrays torna o algoritmo linear, e dois ponteiros que sempre avançam pelo lado mais baixo não precisam de arrays.
Examine os dois lados de cada barra
Correta, mas não termina nos maiores testes
Intuição
Conte a água coluna por coluna. A água acima da barra i sobe até transbordar pela parede mais baixa das duas. A parede esquerda é a barra mais alta em qualquer posição do índice 0 até i; a parede direita é a barra mais alta do índice i até o final. Portanto, o nível é min(leftMax, rightMax), e a água acima da barra i é esse nível menos height[i].
Considere [0, 3, 1, 0, 2, 5, 1, 2] e a barra de altura 0 no índice 3. A barra mais alta à esquerda tem altura 3; à direita, 5. O nível é 3, então ficam 3 unidades ali. Para a barra de altura 1 no índice 6, as paredes têm alturas 5 e 2: o nível é 2 e ela retém 1 unidade.
As duas varreduras incluem a própria barra i. Isso impede que o resultado fique negativo: quando a barra i é mais alta do que tudo de um dos lados, o máximo desse lado é a altura dela própria, o nível é igual à sua altura e ela retém 0. É também por isso que a primeira e a última barras sempre retêm 0.
O problema é o custo. Cada barra percorre toda a linha, metade à esquerda e metade à direita, totalizando n × n leituras: 4 × 10^8 para 2 × 10^4 barras. As varreduras também repetem trabalho: a barra mais alta à esquerda do índice 5 é a barra mais alta à esquerda do índice 4 mais uma comparação, mas a força bruta a recalcula desde o início.
Algoritmo
- Defina
watercomo 0. - Para cada índice
i, percorra do 0 atéipara encontrarleftMax. - Percorra de
iaté o último índice para encontrarrightMax. - Some
min(leftMax, rightMax) - height[i]awater. - Retorne
water.
def trap(height):
n = len(height)
water = 0
for i in range(n):
# The tallest bar at or left of i, and the tallest at or right of i.
left_max = 0
for j in range(i + 1):
left_max = max(left_max, height[j])
right_max = 0
for j in range(i, n):
right_max = max(right_max, height[j])
water += min(left_max, right_max) - height[i]
return waterPré-calcule a barra mais alta de cada lado
Intuição
A fórmula continua igual; só muda a maneira de obter as duas paredes. A barra mais alta de 0 até i é a maior entre a barra mais alta de 0 até i-1 e height[i]. Assim, uma passagem da esquerda para a direita preenche um array leftMax, com cada elemento construído a partir do anterior. Uma passagem da direita para a esquerda preenche rightMax da mesma maneira. Uma terceira passagem soma min(leftMax[i], rightMax[i]) - height[i] para cada barra.
Para [0, 3, 1, 0, 2, 5, 1, 2]: leftMax = [0, 3, 3, 3, 3, 5, 5, 5] e rightMax = [5, 5, 5, 5, 5, 5, 2, 2]. Os menores valores entre eles são os níveis [0, 3, 3, 3, 3, 5, 2, 2]. Subtraia as alturas e você obtém [0, 0, 2, 3, 1, 0, 1, 0], cuja soma é 7.
Cada passagem percorre cada barra uma vez, então o tempo é O(n): cerca de 6 × 10^4 etapas para 2 × 10^4 barras, em vez de 4 × 10^8. O custo são dois arrays extras com n números. Esta é a versão a que você deve recorrer primeiro em uma entrevista: é difícil errar, e a próxima abordagem é uma maneira de eliminar os arrays, não uma ideia diferente.
Algoritmo
- Preencha
leftMaxda esquerda para a direita:leftMax[0] = height[0], depoisleftMax[i] = max(leftMax[i-1], height[i]). - Preencha
rightMaxda direita para a esquerda:rightMax[n-1] = height[n-1], depoisrightMax[i] = max(rightMax[i+1], height[i]). - Para cada índice, some
min(leftMax[i], rightMax[i]) - height[i]ao total. - Retorne o total.
def trap(height):
n = len(height)
left_max = [0] * n # tallest bar from index 0 to i
right_max = [0] * n # tallest bar from index i to n-1
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return waterDois ponteiros que movem o lado inferior
Intuição
A fórmula precisa apenas da menor das duas paredes. Se você puder provar que a parede da esquerda é a menor em algum índice, nunca precisará da parede da direita desse índice. Dois ponteiros fornecem essa prova. Coloque left no índice 0 e right no último índice, e mantenha leftMax e rightMax, a barra mais alta por onde cada ponteiro já passou, incluindo a barra sobre a qual está.
O invariante: toda barra pela qual os ponteiros já passaram não é mais alta do que a barra mais alta das duas sobre as quais estão agora. Isso é válido porque você sempre move o ponteiro na barra mais baixa; assim, um ponteiro só passa por uma barra que não é mais alta do que a barra sob o outro ponteiro.
Agora suponha que height[left] < height[right]. Pelo invariante, leftMax é no máximo height[right], e height[right] é uma barra à direita de left. Portanto, a verdadeira parede direita de left tem pelo menos a altura de leftMax, e o nível em left é exatamente leftMax, independentemente do que esteja entre os ponteiros. Some leftMax - height[left] e mova left um passo para a direita. Quando height[right] for a barra mais baixa ou tiver a mesma altura, faça o procedimento espelhado no lado direito. Atualize o máximo acumulado antes de somar a água, para que a barra sob o ponteiro conte como sua própria parede e a quantidade de água nunca seja negativa.
Percorra [0, 3, 1, 0, 2, 5, 1, 2]. Os ponteiros começam em 0 e 2: a barra da esquerda é mais baixa e retém 0. Em seguida, 3 contra 2: a da direita é mais baixa, rightMax passa a ser 2 e ela retém 0. Depois, 3 contra 1: a da direita é mais baixa novamente, e a barra de altura 1 retém 2-1 = 1. Então, 3 contra 5: agora a barra da esquerda é mais baixa, leftMax é 3, a barra de altura 3 retém 0, a de altura 1 retém 2, a de altura 0 retém 3 e a de altura 2 retém 1. Os ponteiros se encontram na barra de altura 5. O total é 1 + 2 + 3 + 1 = 7, com uma única passada e quatro variáveis.
Algoritmo
- Defina
left = 0,right = n-1eleftMax,rightMaxewatercomo 0. - Enquanto
left < right, compareheight[left]comheight[right]. - Se a barra da esquerda for mais baixa, aumente
leftMaxparaheight[left], se necessário, someleftMax - height[left]e movaleftpara a direita. - Caso contrário, aumente
rightMaxparaheight[right], se necessário, somerightMax - height[right]e movarightpara a esquerda. - Retorne
waterquando os ponteiros se encontrarem; a barra em que eles se encontram é a mais alta e não retém água.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0 # tallest bar passed so far from each end
water = 0
while left < right:
if height[left] < height[right]:
# A bar taller than height[left] waits on the right, so left_max sets the level here.
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
# A bar at least as tall as height[right] waits on the left, so right_max sets the level.
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
Armadilhas e casos extremos
A fórmula é curta, e a maioria das respostas erradas decorre da ordem de duas linhas ou de qual lado você move.
- Adicionar a água antes de atualizar o máximo acumulado. Se
height[left]for maior queleftMax,leftMax - height[left]é negativo e o total diminui. Atualize primeiro o máximo e, depois, adicione. - Mover o ponteiro na barra mais alta. O nível só é conhecido no lado mais baixo; mover o lado mais alto usa uma parede que você ainda não comprovou. Em
[4, 1, 3, 0, 5], essa versão retorna 4 em vez de 8. - Considerar apenas os vizinhos mais próximos. As paredes de uma barra podem estar bem longe: em
[3, 0, 2, 0, 1, 0, 4], a barra de 1 retém água até o nível 3, definido por barras a quatro e dois passos de distância. A resposta nesse caso é 12. - Tratar as extremidades do array como paredes. A água além da primeira ou da última barra escorre, então uma única barra, duas barras ou uma sequência que só sobe ou só desce retém 0.
- Excluir a barra
ide suas próprias verificações na força bruta. Assim, uma barra mais alta que ambos os lados resulta em uma quantidade negativa. Inclua-a ou limite o resultado a 0. - Overflow em uma variante que multiplica. Aqui, a resposta chega a cerca de 2 × 10^9 (duas barras de 10^5 em torno de 19,998 células vazias), o que ainda cabe em um inteiro com sinal de 32 bits; em suas próprias variantes, use somas de 64 bits.
Perguntas frequentes4
Qual é a complexidade de tempo do problema de retenção de água da chuva?
A solução com dois ponteiros executa em tempo O(n) e usa O(1) de espaço extra: a cada etapa, um ponteiro avança para dentro, então há n-1 etapas. A versão com os arrays leftMax e rightMax também executa em tempo O(n), mas usa O(n) de espaço. Percorrer ambos os lados a partir de cada barra é O(n²), cerca de 4 × 10^8 leituras para 2 × 10^4 barras.
Por que a solução com dois ponteiros pode mover o lado mais curto?
Cada barra já ultrapassada não é mais alta do que a mais alta das duas barras atuais, porque apenas o ponteiro inferior se move. Portanto, quando a barra da esquerda é mais baixa, sua altura máxima até então é, no máximo, a da barra da direita, e a barra da direita é uma parede real à sua direita. O nível no ponteiro da esquerda corresponde à altura máxima até então, independentemente do que houver entre os ponteiros, então você pode contabilizar essa barra e seguir em frente.
É possível resolver o problema de reter água da chuva usando uma pilha?
Sim. Mantenha uma pilha de índices cujas alturas aumentam da base para o topo. Quando chegar uma barra mais alta que a do topo, remova o topo: ele é o fundo de uma poça cujas paredes são o novo topo da pilha e a barra atual. Adicione (min(two walls) - floor) × (distance between the walls - 1) e continue removendo elementos enquanto a barra atual for mais alta. A pilha preenche a água em camadas horizontais em vez de colunas, em O(n) de tempo e O(n) de espaço.
Qual é a diferença entre Trapping Rain Water e Container With Most Water?
Em Container With Most Water, você escolhe duas linhas, e as linhas entre elas não ocupam espaço, então a resposta é um retângulo, o maior possível. Aqui, cada barra é sólida, a água fica em cima de cada barra, e a resposta é a soma de todas as barras. Ambos usam dois ponteiros que movem o lado mais baixo, pelo mesmo motivo: o resultado do lado mais baixo já está determinado.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def trap(height):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
height = [0, 3, 1, 0, 2, 5, 1, 2]
Esperado
7