Go の 2 つのポインターを使用してコンテナー領域を最大化する
配列またはリストを扱うアルゴリズムでは、2 ポインター手法がその効率性の点で際立っています。 この記事では、グラフ上の 2 本の垂直線の間の最大面積を求める古典的な「最も水が入った容器」問題にそれを適用します。
問題の説明
垂直線の高さを表す非負の整数の配列が与えられた場合、x 軸とともに最大面積のコンテナを形成する線のペアを見つけます。
例
配列 height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
について考えてみましょう。 目的は、どの 2 つの線が最大面積を生成するかを決定することです。
ツーポインターテクニック
この手法では、2 つのポインターを使用し、1 つは配列の先頭に、もう 1 つは配列の末尾に配置し、それらを中心に向かって繰り返し移動させて、最適なソリューションを見つけます。
ステップバイステップ
-
起動時:
-
maxArea
は 0 に初期化され、これまでに見つかった最大の領域が格納されます。 - 2 つのポインター、
l
(左) とr
(右) は、それぞれ配列の先頭と末尾に配置されます。
-
-
反復:
- ループは、
l
がr
未満である限り継続します。 -
l
とr
の線の間の領域はmin(height[l], height[r]) * (r - l)
として計算されます。 -
maxArea
は、計算された領域が大きい場合に更新されます。
- ループは、
-
ポインタの移動:
- 検索を最適化するために、小さい方の線を指すポインタを移動します。
height[l] の場合、<code>l
をインクリメントします。- それ以外の場合は、
r
をデクリメントします。
- 検索を最適化するために、小さい方の線を指すポインタを移動します。
-
戻る:
-
l
とr
が交差するとループは終了し、maxArea
には最大領域が含まれます。
-
詳細な例
配列 height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
を分析しましょう:
-
起動時:
maxArea = 0
-
l = 0
(高さ 1)、r = 8
(高さ 7)
-
最初の反復:
- エリア:
min(1, 7) * (8 - 0) = 8
maxArea = max(0, 8) = 8
-
l
を移動します (height[l] のため)
- エリア:
-
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 サイトの他の関連記事を参照してください。

この記事では、Goのパッケージインポートメカニズム:名前付きインポート(例:インポート "fmt&quot;)および空白のインポート(例:_&quot; fmt&quot;)について説明しています。 名前付きインポートはパッケージのコンテンツにアクセス可能になり、空白のインポートはtのみを実行します

この記事では、Webアプリケーションでのページ間データ転送のためのBeegoのnewflash()関数について説明します。 newflash()を使用して、コントローラー間で一時的なメッセージ(成功、エラー、警告)を表示し、セッションメカニズムを活用することに焦点を当てています。 リミア

この記事では、MySQLクエリの結果をGO structスライスに効率的に変換することを詳しく説明しています。 データベース/SQLのスキャン方法を使用して、手動で解析することを避けて強調しています。 DBタグとロブを使用した構造フィールドマッピングのベストプラクティス

この記事では、ユニットテストのためにGOのモックとスタブを作成することを示しています。 インターフェイスの使用を強調し、模擬実装の例を提供し、模擬フォーカスを維持し、アサーションライブラリを使用するなどのベストプラクティスについて説明します。 articl

この記事では、GENICSのGOのカスタムタイプの制約について説明します。 インターフェイスがジェネリック関数の最小タイプ要件をどのように定義するかを詳しく説明し、タイプの安全性とコードの再利用性を改善します。 この記事では、制限とベストプラクティスについても説明しています

この記事では、goで効率的なファイルの書き込みを詳しく説明し、os.writefile(小さなファイルに適している)とos.openfileおよびbuffered write(大規模ファイルに最適)と比較します。 延期エラー処理、Deferを使用し、特定のエラーをチェックすることを強調します。

この記事では、GOでユニットテストを書くことで、ベストプラクティス、モッキングテクニック、効率的なテスト管理のためのツールについて説明します。

この記事では、トレースツールを使用してGOアプリケーションの実行フローを分析します。 手動および自動計装技術について説明し、Jaeger、Zipkin、Opentelemetryなどのツールを比較し、効果的なデータの視覚化を強調しています


ホットAIツール

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

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

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

AI Hentai Generator
AIヘンタイを無料で生成します。

人気の記事

ホットツール

Safe Exam Browser
Safe Exam Browser は、オンライン試験を安全に受験するための安全なブラウザ環境です。このソフトウェアは、あらゆるコンピュータを安全なワークステーションに変えます。あらゆるユーティリティへのアクセスを制御し、学生が無許可のリソースを使用するのを防ぎます。

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

ZendStudio 13.5.1 Mac
強力な PHP 統合開発環境

SublimeText3 Linux 新バージョン
SublimeText3 Linux 最新バージョン

メモ帳++7.3.1
使いやすく無料のコードエディター

ホットトピック









