두 포인터 기술

Go에서 두 개의 포인터로 컨테이너 영역 최대화

배열이나 목록을 사용하는 알고리즘에서 2포인터 기술은 효율성이 돋보입니다. 이 글에서는 그래프에서 두 수직선 사이의 가장 큰 면적을 찾는 고전적인 "물이 가장 많은 용기" 문제에 이를 적용해 보겠습니다.

문제 설명

세로선의 높이를 나타내는 음이 아닌 정수 배열이 주어지면 x축과 함께 가장 큰 면적을 갖는 컨테이너를 형성하는 선 쌍을 찾습니다.

예

배열을 고려해보세요height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. 목표는 어느 두 선이 최대 면적을 생성하는지 결정하는 것입니다.

두 포인터 기법

이 기술은 두 개의 포인터(배열의 시작 부분과 끝 부분)를 사용하여 반복적으로 중앙을 향해 이동하여 최적의 솔루션을 찾습니다.

차근차근

1. 스타트업:

   • maxArea은 0으로 초기화되어 지금까지 발견된 가장 큰 영역을 저장합니다.
   • 두 개의 포인터 l(왼쪽)과 r(오른쪽)은 각각 배열의 시작과 끝 부분에 위치합니다.

2. 반복:

   • l이 r보다 작은 한 루프가 계속됩니다.
   • l과 r의 선 사이의 면적은 min(height[l], height[r]) * (r - l)으로 계산됩니다.
   • maxArea 계산된 면적이 커지면 업데이트됩니다.

3. 포인터 이동:

   • 검색을 최적화하기 위해 더 작은 줄을 가리키는 포인터가 이동됩니다.
     • height[l] 인 경우 <code>l을 증가시킵니다.
     • 그렇지 않으면 감소 r.

4. 반품:

   • l과 r가 교차하면 루프가 종료되고 maxArea에는 최대 영역이 포함됩니다.

상세 예시

배열을 분석해 보겠습니다 height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

1. 스타트업:

   • maxArea = 0
   • l = 0(높이 1), r = 8(높이 7)

2. 첫 번째 반복:

   • 지역: min(1, 7) * (8 - 0) = 8
   • maxArea = max(0, 8) = 8
   • 이동 l (height[l] 때문에)

3. 두 번째 반복:

   • l = 1(높이 8), r = 8(높이 7)
   • 지역: min(8, 7) * (8 - 1) = 49
   • maxArea = max(8, 49) = 49
   • 이동 r

...등등 손이 닿을 때까지 이 과정을 반복합니다.

최종 결과는 maxArea = 49입니다.

솔루션 바로가기

기술을 구현하는 Go 코드를 따르세요.

package maxarea

func maxArea(height []int) int {
    maxArea := 0
    l, r := 0, len(height)-1

    for l < r {
        area := min(height[l], height[r]) * (r - l)
        maxArea = max(maxArea, area)
        if height[l] < height[r] {
            l++
        } else {
            r--
        }
    }
    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

결론

두 포인터 기술은 배열과 관련된 문제에 대한 효율적인 솔루션을 제공합니다. "Container With Most Water"의 경우 선형 시간 복잡도를 보장하므로 이상적인 접근 방식입니다.

위 내용은 두 포인터 기술의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!