A técnica dos dois ponteiros
Maximização da Área do Contêiner com Dois Ponteiros em Go Ao resolver problemas que envolvem arrays ou listas, a técnica dos dois ponteiros é uma estratégia poderosa e eficiente. Neste artigo, vamos explorar como usar essa técnica para resolver o problema "Container With Most Water", que envolve encontrar a área máxima entre duas linhas verticais em um gráfico. Enunciado do Problema Dado um array de inteiros não negativos onde cada inteiro representa a altura de uma linha vertical em um gráfico, encontre duas linhas que, junto com o eixo x, formem um contêiner que contenha a maior quantidade de água. Exemplo Vamos considerar o array height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. O objetivo é encontrar as duas linhas que formam o contêiner com a área máxima. Técnica dos Dois Ponteiros A técnica dos dois ponteiros envolve inicializar dois ponteiros no início e no final do array e movê-los em direção um ao outro para encontrar a solução ideal. Explicação Passo a Passo Inicialização: maxArea é inicializado como 0 para armazenar a maior área encontrada. Dois ponteiros, l (esquerda) e r (direita), são inicializados no início e no final do array, respectivamente. Iteração: Enquanto l for menor que r, o loop continua. A área entre as linhas nos índices l e r é calculada como min(height[l], height[r]) * (r - l). maxArea é atualizado se a área calculada for maior que o valor atual de maxArea. Movimento dos Ponteiros: Para potencialmente encontrar uma área maior, o ponteiro que aponta para a linha mais curta é movido: Se height[l] for menor que height[r], incremente l. Caso contrário, decremente r. Retorno: Quando os ponteiros se encontram, o loop termina, e maxArea é retornado como a maior área encontrada. Exemplo Passo a Passo Vamos percorrer o exemplo height = [1, 8, 6, 2, 5, 4, 8, 3, 7] passo a passo: Inicialização: maxArea = 0 Ponteiros: l = 0 (altura 1) e r = 8 (altura 7) Primeira Iteração: Área: min(1, 7) * (8 - 0) = 1 * 8 = 8 Atualiza maxArea: maxArea = max(0, 8) = 8 Move l (já que height[l] < height[r]): l = 1 Segunda Iteração: Ponteiros: l = 1 (altura 8) e r = 8 (altura 7) Área: min(8, 7) * (8 - 1) = 7 * 7 = 49 Atualiza maxArea: maxArea = max(8, 49) = 49 Move r: r = 7 Terceira Iteração: Ponteiros: l = 1 (altura 8) e r = 7 (altura 3) Área: min(8, 3) * (7 - 1) = 3 * 6 = 18 maxArea permanece 49 Move r: r = 6 Quarta Iteração: Ponteiros: l = 1 (altura 8) e r = 6 (altura 8) Área: min(8, 8) * (6 - 1) = 8 * 5 = 40 maxArea permanece 49 Move r: r = 5 Quinta Iteração: Ponteiros: l = 1 (altura 8) e r = 5 (altura 4) Área: min(8, 4) * (5 - 1) = 4 * 4 = 16 maxArea permanece 49 Move r: r = 4 Sexta Iteração: Ponteiros: l = 1 (altura 8) e r = 4 (altura 5) Área: min(8, 5) * (4 - 1) = 5 * 3 = 15 maxArea permanece 49 Move r: r = 3 Sétima Iteração: Ponteiros: l = 1 (altura 8) e r = 3 (altura 2) Área: min(8, 2) * (3 - 1) = 2 * 2 = 4 maxArea permanece 49 Move r: r = 2 Oitava Iteração: Ponteiros: l = 1 (altura 8) e r = 2 (altura 6) Área: min(8, 6) * (2 - 1) = 6 * 1 = 6 maxArea permanece 49 Move r: r = 1 Fim do Loop: Os ponteiros se encontram (l = r), então o loop termina. O valor final de maxArea é 49, que é a maior área possível entre duas linhas no array height. Solução em Go Aqui está o código completo em Go implementando a técnica dos dois ponteiros: package maxarea func maxArea(height []int) int { maxArea := 0 l, r := 0, len(height)-1 for l
Maximização da Área do Contêiner com Dois Ponteiros em Go
Ao resolver problemas que envolvem arrays ou listas, a técnica dos dois ponteiros é uma estratégia poderosa e eficiente. Neste artigo, vamos explorar como usar essa técnica para resolver o problema "Container With Most Water", que envolve encontrar a área máxima entre duas linhas verticais em um gráfico.
Enunciado do Problema
Dado um array de inteiros não negativos onde cada inteiro representa a altura de uma linha vertical em um gráfico, encontre duas linhas que, junto com o eixo x, formem um contêiner que contenha a maior quantidade de água.
Exemplo
Vamos considerar o array height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
. O objetivo é encontrar as duas linhas que formam o contêiner com a área máxima.
Técnica dos Dois Ponteiros
A técnica dos dois ponteiros envolve inicializar dois ponteiros no início e no final do array e movê-los em direção um ao outro para encontrar a solução ideal.
Explicação Passo a Passo
-
Inicialização:
-
maxArea
é inicializado como 0 para armazenar a maior área encontrada. - Dois ponteiros,
l
(esquerda) er
(direita), são inicializados no início e no final do array, respectivamente.
-
-
Iteração:
- Enquanto
l
for menor quer
, o loop continua. - A área entre as linhas nos índices
l
er
é calculada comomin(height[l], height[r]) * (r - l)
. -
maxArea
é atualizado se a área calculada for maior que o valor atual demaxArea
.
- Enquanto
-
Movimento dos Ponteiros:
- Para potencialmente encontrar uma área maior, o ponteiro que aponta para a linha mais curta é movido:
- Se
height[l]
for menor queheight[r]
, incrementel
. - Caso contrário, decremente
r
.
- Se
- Para potencialmente encontrar uma área maior, o ponteiro que aponta para a linha mais curta é movido:
-
Retorno:
- Quando os ponteiros se encontram, o loop termina, e
maxArea
é retornado como a maior área encontrada.
- Quando os ponteiros se encontram, o loop termina, e
Exemplo Passo a Passo
Vamos percorrer o exemplo height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
passo a passo:
-
Inicialização:
maxArea = 0
- Ponteiros:
l = 0
(altura 1) er = 8
(altura 7)
-
Primeira Iteração:
- Área:
min(1, 7) * (8 - 0) = 1 * 8 = 8
- Atualiza
maxArea
:maxArea = max(0, 8) = 8
- Move
l
(já queheight[l] < height[r]
):l = 1
- Área:
-
Segunda Iteração:
- Ponteiros:
l = 1
(altura 8) er = 8
(altura 7) - Área:
min(8, 7) * (8 - 1) = 7 * 7 = 49
- Atualiza
maxArea
:maxArea = max(8, 49) = 49
- Move
r
:r = 7
- Ponteiros:
-
Terceira Iteração:
- Ponteiros:
l = 1
(altura 8) er = 7
(altura 3) - Área:
min(8, 3) * (7 - 1) = 3 * 6 = 18
-
maxArea
permanece 49 - Move
r
:r = 6
- Ponteiros:
-
Quarta Iteração:
- Ponteiros:
l = 1
(altura 8) er = 6
(altura 8) - Área:
min(8, 8) * (6 - 1) = 8 * 5 = 40
-
maxArea
permanece 49 - Move
r
:r = 5
- Ponteiros:
-
Quinta Iteração:
- Ponteiros:
l = 1
(altura 8) er = 5
(altura 4) - Área:
min(8, 4) * (5 - 1) = 4 * 4 = 16
-
maxArea
permanece 49 - Move
r
:r = 4
- Ponteiros:
-
Sexta Iteração:
- Ponteiros:
l = 1
(altura 8) er = 4
(altura 5) - Área:
min(8, 5) * (4 - 1) = 5 * 3 = 15
-
maxArea
permanece 49 - Move
r
:r = 3
- Ponteiros:
-
Sétima Iteração:
- Ponteiros:
l = 1
(altura 8) er = 3
(altura 2) - Área:
min(8, 2) * (3 - 1) = 2 * 2 = 4
-
maxArea
permanece 49 - Move
r
:r = 2
- Ponteiros:
-
Oitava Iteração:
- Ponteiros:
l = 1
(altura 8) er = 2
(altura 6) - Área:
min(8, 6) * (2 - 1) = 6 * 1 = 6
-
maxArea
permanece 49 - Move
r
:r = 1
- Ponteiros:
-
Fim do Loop:
- Os ponteiros se encontram (
l = r
), então o loop termina.
- Os ponteiros se encontram (
O valor final de maxArea
é 49, que é a maior área possível entre duas linhas no array height
.
Solução em Go
Aqui está o código completo em Go implementando a técnica dos dois ponteiros:
package maxarea
func maxArea(height []int) int {
maxArea := 0
l, r := 0, len(height)-1
for l < r {
maxArea = max(maxArea, min(height[l], height[r])*(r-l))
if height[l] < height[r] {
l++
} else {
r--
}
}
return maxArea
}
Conclusão
A técnica dos dois ponteiros é uma ferramenta poderosa para resolver problemas que envolvem arrays ou listas. Movendo os ponteiros de forma inteligente, podemos encontrar a solução ideal de maneira eficiente.
No problema "Container With Most Water", essa técnica nos permite encontrar a área máxima entre duas linhas em tempo linear