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. A chuva se acumula nas depressões entre as barras. A água fica acima de uma barra somente 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 total de unidades de água que a fileira retém.
Função
- heightinteger-array
- a altura de cada barra, da esquerda para a direita
- Retornainteger
- a quantidade 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, o nível é 3: 2 unidades acima do 1, 3 acima do 0, 1 acima do 2. O 1 seguinte fica entre o 5 e um 2, então vale 1. Isso dá 7.
- Entrada
- height = [4, 1, 3, 0, 5]
- Saída
- 8
- Explicação
- A parede mais baixa é a 4, então a depressão se enche até o nível 4: 3 unidades sobre o 1, 1 sobre o 3, 4 sobre o 0, o que resulta em 8. A água transborda pelo 4 antes que o 5 faça diferença.
- 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.
Para ir além
Suponha que as barras formem uma grade 2D de alturas e que a água possa escapar em todas as 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. Qual é a altura que a água pode atingir acima da barra
i, e quais barras determinam essa altura?O nível da água acima da barra
ié o menor entre 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 pela qual cada ponteiro já passou. O nível do ponteiro que estiver na 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 uma barra depende de barras que podem estar bem distantes, em ambos os lados. Seu nível é o menor entre a barra mais alta à sua esquerda e a barra mais alta à sua direita, e a barra retém esse nível menos sua própria altura. As abordagens diferem apenas na maneira como encontram esses dois valores máximos.
Examine os dois lados de cada barra
Correta, mas não termina nos maiores testes
Intuição
Para cada barra i, percorra de 0 até i para encontrar a barra mais alta à esquerda e de i até o final para encontrar a mais alta à direita; em seguida, some min(leftMax, rightMax) - height[i]. Incluir a barra i em ambas as varreduras impede que a quantidade fique negativa e resulta em 0 para as barras das extremidades.
Cada barra percorre a linha inteira: n = 2 × 10^4 significa 4 × 10^8 leituras, a maioria repetindo a varredura da barra anterior.
Algoritmo
- Defina
watercomo 0. - Para cada índice
i, percorra de 0 atéipara encontrarleftMax. - Percorra de
iaté o último índice para encontrarrightMax. - Adicione
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 barra mais alta de 0 até i é a maior entre a barra mais alta de 0 até i-1 e height[i]. Então, uma passagem da esquerda para a direita preenche leftMax, cada entrada construída a partir da anterior, e uma passagem da direita para a esquerda preenche rightMax. Uma terceira passagem aplica a fórmula.
Para [0, 3, 1, 0, 2, 5, 1, 2], os níveis min(leftMax[i], rightMax[i]) são [0, 3, 3, 3, 3, 5, 2, 2]. Subtraindo as alturas, temos [0, 0, 2, 3, 1, 0, 1, 0], cuja soma é 7. O tempo é O(n), ao custo de dois arrays com n números.
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, adicione
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 parede menor, e dois ponteiros podem provar qual é ela. Comece com left em 0 e right no último índice, acompanhe leftMax e rightMax, a barra mais alta pela qual cada ponteiro passou, incluindo a própria, e sempre mova o ponteiro na barra mais baixa. Então todas as barras pelas quais já passou não são mais altas que a mais alta das duas barras atuais, pois um ponteiro só passa por uma barra que não seja mais alta que a que está sob o outro ponteiro.
Suponha que height[left] < height[right]. Pelo invariante, leftMax é no máximo height[right], uma barra à direita de left. Portanto, a parede à direita de left tem altura de pelo menos leftMax, e seu nível é exatamente leftMax, independentemente do que esteja entre os ponteiros. Quando a barra da direita é mais baixa ou igual, o argumento simétrico resolve right.
Algoritmo
- Defina
left = 0,right = n-1, eleftMax,rightMaxewatercomo 0. - Enquanto
left < right: seheight[left] < height[right], aumenteleftMaxparaheight[left], se necessário, someleftMax - height[left]e movaleftpara a direita. - Caso contrário, faça o mesmo no lado direito e mova
rightpara a esquerda. - Retorne
water. A barra onde os ponteiros 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
- Adicionar a água antes de atualizar o máximo corrente. Quando
height[left]é maior queleftMax, a quantidade é negativa e o total diminui. - Mover o ponteiro da barra mais alta, cujo nível não está determinado. Em
[4, 1, 3, 0, 5], essa versão retorna 4 em vez de 8. - Considerar apenas as barras vizinhas mais próximas. Em
[3, 0, 2, 0, 1, 0, 4], a barra de altura 1 se enche até o nível 3, definido pelas barras que estão a quatro e a dois passos de distância; a resposta é 12. - Tratar as extremidades do array como paredes. A água escorre por elas; portanto, uma barra, duas barras ou uma sequência que só sobe ou só desce retém 0.
Perguntas frequentes3
Qual é a complexidade de tempo do problema de armazenar água da chuva?
A solução com dois ponteiros é executada em O(n) de tempo e usa O(1) de espaço extra, já que cada etapa move um ponteiro para dentro. A versão com os arrays leftMax e rightMax também é O(n) em tempo, mas usa O(n) de espaço. Percorrer os dois lados a partir de cada barra é O(n²).
É possível resolver o problema da água da chuva acumulada usando uma pilha?
Sim. Mantenha uma pilha de índices com alturas decrescentes. Quando uma barra mais alta chega, remova o elemento do topo: ele é o fundo de uma piscina cercada pela nova barra do topo e pela barra atual. Some (min(two walls) - floor) × (distance between the walls - 1) e continue removendo elementos. Isso preenche a água em camadas horizontais, em O(n) de tempo e espaço.
Qual é a diferença entre Trapping Rain Water e Container With Most Water?
Em Container With Most Water, as linhas não ocupam espaço, e a resposta é o maior retângulo entre duas linhas. Aqui, cada barra é sólida, e a resposta soma a água sobre todas as barras. Em ambos os casos, move-se o lado mais baixo pelo mesmo motivo: seu resultado já está determinado.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def trap(height):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
height = [0, 3, 1, 0, 2, 5, 1, 2]
Saída Esperada
7