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

1. 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.

2. 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.

3. 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.

4. 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:

1. Inicialização:

   • maxArea = 0
   • Ponteiros: l = 0 (altura 1) e r = 8 (altura 7)

2. 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

3. 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

4. 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

5. 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

6. 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

7. 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

8. 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

9. 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

10. 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 < 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