検索
ホームページバックエンド開発Golangツーポインターテクニック

A técnica dos dois ponteiros

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. 反復:

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

    • 検索を最適化するために、小さい方の線を指すポインタを移動します。
      • height[l] の場合、<code>lをインクリメントします。
      • それ以外の場合は、r をデクリメントします。
  4. 戻る:

    • lr が交差するとループは終了し、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. 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 サイトの他の関連記事を参照してください。

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
「文字列」をどのように使用しますかGoで文字列を操作するパッケージ?「文字列」をどのように使用しますかGoで文字列を操作するパッケージ?Apr 30, 2025 pm 02:34 PM

この記事では、弦の操作にGOの「文字列」パッケージを使用し、効率を高め、ユニコードを効果的に処理するための一般的な機能とベストプラクティスの詳細を説明します。

「crypto」をどのように使用しますかGoで暗号化操作を実行するパッケージ?「crypto」をどのように使用しますかGoで暗号化操作を実行するパッケージ?Apr 30, 2025 pm 02:33 PM

記事の詳細は、暗号化操作のためのGoの「暗号」パッケージ、安全な実装のための主要な生成、管理、およびベストプラクティスについて議論するためのパッケージ。

「時間」をどのように使用しますかGOの日付と時間を処理するパッケージ?「時間」をどのように使用しますかGOの日付と時間を処理するパッケージ?Apr 30, 2025 pm 02:32 PM

この記事では、現在の時間の取得、特定の時間の作成、文字列の解析、経過時間の測定など、日付、時間、およびタイムゾーンを処理するためのGoの「時間」パッケージの使用について詳しく説明しています。

「反射」をどのように使用しますかGOの変数のタイプと値を検査するパッケージ?「反射」をどのように使用しますかGOの変数のタイプと値を検査するパッケージ?Apr 30, 2025 pm 02:29 PM

記事では、可変検査と変更のためにGOの「反射」パッケージを使用して、方法とパフォーマンスの考慮事項を強調するために説明します。

「sync/atomic」をどのように使用しますかゴーでアトミック操作を実行するパッケージ?「sync/atomic」をどのように使用しますかゴーでアトミック操作を実行するパッケージ?Apr 30, 2025 pm 02:26 PM

この記事では、同時プログラミングにおけるGoの「Sync/Atomic」パッケージを使用して、人種の条件の防止やパフォーマンスの改善などの利点を詳述していることについて説明します。

GOでタイプ変換を作成して使用するための構文は何ですか?GOでタイプ変換を作成して使用するための構文は何ですか?Apr 30, 2025 pm 02:25 PM

この記事では、構文、安全な変換慣行、一般的な落とし穴、学習リソースなど、GOのタイプ変換について説明します。明示的なタイプの変換とエラー処理を強調しています。[159文字]

GOでタイプアサーションを作成して使用するための構文は何ですか?GOでタイプアサーションを作成して使用するための構文は何ですか?Apr 30, 2025 pm 02:24 PM

この記事では、構文、パニックや誤ったタイプなどの潜在的なエラー、安全な取り扱い方法、パフォーマンスへの影響に焦点を当てたGOのタイプアサーションについて説明します。

&quot; select&quot;をどのように使用しますかGo?の声明?&quot; select&quot;をどのように使用しますかGo?の声明?Apr 30, 2025 pm 02:23 PM

この記事では、複数のチャネル操作を処理するためのGOの「選択」ステートメントの使用、「スイッチ」ステートメントとの違い、および複数のチャネルの処理、タイムアウトの実装、Non-Bなどの一般的なユースケースについて説明します。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

PhpStorm Mac バージョン

PhpStorm Mac バージョン

最新(2018.2.1)のプロフェッショナル向けPHP統合開発ツール

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境

mPDF

mPDF

mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。

EditPlus 中国語クラック版

EditPlus 中国語クラック版

サイズが小さく、構文の強調表示、コード プロンプト機能はサポートされていません