A técnica dos dois ponteiros

#go #twopointer #leetcode #algorithms

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

DEV Community