ツーポインターテクニック

Go の 2 つのポインターを使用してコンテナー領域を最大化する

配列またはリストを扱うアルゴリズムでは、2 ポインター手法がその効率性の点で際立っています。 この記事では、グラフ上の 2 本の垂直線の間の最大面積を求める古典的な「最も水が入った容器」問題にそれを適用します。

問題の説明

垂直線の高さを表す非負の整数の配列が与えられた場合、x 軸とともに最大面積のコンテナを形成する線のペアを見つけます。

例

配列 height = [1, 8, 6, 2, 5, 4, 8, 3, 7] について考えてみましょう。 目的は、どの 2 つの線が最大面積を生成するかを決定することです。

ツーポインターテクニック

この手法では、2 つのポインターを使用し、1 つは配列の先頭に、もう 1 つは配列の末尾に配置し、それらを中心に向かって繰り返し移動させて、最適なソリューションを見つけます。

ステップバイステップ

1. 起動時:

   • maxArea は 0 に初期化され、これまでに見つかった最大の領域が格納されます。
   • 2 つのポインター、l (左) と r (右) は、それぞれ配列の先頭と末尾に配置されます。

2. 反復:

   • ループは、l が r 未満である限り継続します。
   • l と r の線の間の領域は min(height[l], height[r]) * (r - l) として計算されます。
   • maxAreaは、計算された領域が大きい場合に更新されます。

3. ポインタの移動:

   • 検索を最適化するために、小さい方の線を指すポインタを移動します。
     • height[l] < height[r]の場合、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] < height[r] のため)

3. 2 番目の反復:

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

結論

2 ポインター手法は、配列に関する問題に対する効率的な解決策を提供します。 「ほとんどの水を含むコンテナ」の場合、線形時間計算量が保証され、理想的なアプローチとなります。

以上がツーポインターテクニックの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。