DEV Community

Cover image for A técnica dos dois ponteiros

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
}
Enter fullscreen mode Exit fullscreen mode

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

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more