【ITニュース解説】Find the Maximum Area possible given different vertical lines on X-Axis (Leetcode Problem Analysis)

このニュース記事は、X軸上に並んだ様々な高さの垂直線の中から2本を選び、それらとX軸で囲まれる領域の最大面積をどのように見つけるかという問題を解説している。この問題は、アルゴリズムの効率性を考える上で非常に良い例となる。

まず、問題の核心を理解する必要がある。与えられた配列の各数字は垂直線の高さを表しており、私たちはこの中から任意の2本の線を選ぶ。選んだ2本の線とX軸で構成される図形は長方形であり、その面積を計算する。長方形の面積は「底辺×高さ」で求められる。この問題の場合、底辺は選んだ2本の線の間の距離となり、高さは2本の線のうち低い方の高さになる。なぜなら、もし高い方の線を高さとしてしまうと、低い方の線から水が溢れ出てしまう、つまり囲われた領域として成立しないからだ。常に低い方の線が水面の高さの限界となる。したがって、最大の面積を見つけるためには、「（2本の線の間の距離）×（2本の線のうち低い方の高さ）」という計算で得られる値が最も大きくなる組み合わせを探すことになる。

この問題を解決するための最初の素朴なアプローチは、「ブルートフォース（力任せ）」と呼ばれる方法である。これは、配列内にある全ての線のペアについて面積を計算し、その中で最大のものを探し出すという単純な手法だ。例えば、最初の線と2番目の線、最初の線と3番目の線、…といった具合に、考えられる全ての組み合わせを一つずつ試していく。しかし、この方法は線の数が増えるにつれて、計算量が爆発的に増大するという大きな欠点がある。もし線の数がn本だとすると、おおよそnの2乗に比例する回数の計算が必要となる。例えば、線が1000本あれば約50万回、1万本あれば約5000万回もの面積計算が必要になり、これは現実的な時間で答えを出すことが非常に困難になる。システムエンジニアとして、このような非効率な方法は避けるべきである。

そこで、より効率的な「2ポインター」というアルゴリズムが考案された。この方法は、計算量を劇的に減らし、線の数nに対しておおよそn回程度の計算で済むようにする。

2ポインターアプローチの具体的な手順は次のようになる。 まず、配列の最も外側にある2本の線、つまり左端と右端の線にそれぞれポインター（目印）を置く。左端のポインターをa、右端のポインターをbと呼ぶことにしよう。この2本の線を選んだ時の底辺の距離はb - aで、これが最も広くなる。そして、この2本の線のうち低い方の高さを採用して面積を計算し、現在の最大面積として記録する。

次に、この2つのポインターを互いに中央に向かって動かしていくことになるが、どちらのポインターを動かすかがこのアルゴリズムの鍵となる。

現在の2本の線h[a]とh[b]を比較し、低い方のポインターを内側に1つ移動させるというルールを採用する。 なぜ低い方のポインターを動かすのか、その理由を詳しく説明する。 現在の面積は、2本の線のうち低い方の高さによって制限されている。例えば、左の線h[a]が右の線h[b]よりも低い場合、面積はh[a] * (b - a)で決まる。この状態で、もし背の高い右の線h[b]を内側に動かしたとしても、新しい右の線がh[a]よりも高かったとしても、現在の面積は依然としてh[a]によって制限される。そして、底辺の距離は確実に短くなるため、面積が大きくなる可能性は非常に低い。

しかし、もし背の低い左の線h[a]を内側に動かしたらどうなるだろうか。確かに底辺の距離は短くなるが、新しい左の位置で、もしかしたら現在のh[a]よりもっと背の高い線h[a+1]を見つけられるかもしれない。その場合、容器の高さが現在のh[a]よりも高くなる可能性があり、底辺の距離が短くなったことを補って余りある、より大きな面積を得られる可能性があるのだ。

このロジックに基づき、私たちは常に背の低い方のポインターを内側に移動させる。この作業を、左ポインターaが右ポインターbと交差するか、追い越すまで繰り返す。各ステップで新しい面積を計算し、これまでの最大面積よりも大きければ更新していく。最終的に、ポインターが交差した時点でループは終了し、それまでに記録された最大面積が答えとなる。この方法により、全ての組み合わせを試すことなく、効率的に最大面積を見つけ出すことができるため、計算量はnに比例する（O(n)）という優れた性能を発揮する。

それでは、このアルゴリズムがJavaのコードでどのように実装されているかを見てみよう。

public int maxArea(int[] h)は、高さの配列hを受け取り、計算された最大面積を整数で返すメソッドである。

int n = h.length, i=0, max=Integer.MIN_VALUE, a=0,b=n-1; ここでいくつかの変数が初期化される。

• nは配列hの長さ（線の総数）である。
• maxはこれまでに計算された最大面積を保持するための変数で、最初はJavaの整数型で表現できる最小値（Integer.MIN_VALUE）に設定されている。これは、どんな有効な面積もこの初期値より必ず大きくなるため、最初の計算で確実にmaxが更新されるようにするためだ。
• aは左ポインターのインデックスで、最初は配列の先頭（0）を指す。
• bは右ポインターのインデックスで、最初は配列の末尾（n-1）を指す。

if(n==1){ return h[0]; } この行は、配列hに要素が1つしかない、つまり垂直線が1本しかないという特殊なケースを処理している。問題の定義では2本の線が必要なため、通常は面積0と考えることが多いが、このコードではその線の高さをそのまま返している。

while(b>a){ ... } これが2ポインターアルゴリズムの主要なループである。左ポインターaが右ポインターbよりも小さい間（つまり、まだポインターが交差していない間）、ループ内の処理が繰り返される。

ループの中では、まず現在の2本の線の高さを比較する。 if(h[a]<h[b]){ ... } もし左ポインターの線h[a]が右ポインターの線h[b]よりも低い場合、面積の高さはh[a]に制限される。 int currentArea = h[a]*(b-a); 現在の面積currentAreaを計算する。高さは低い方のh[a]、底辺は2つのポインター間の距離であるb-aとなる。 if(max<currentArea) max=currentArea; 計算されたcurrentAreaが現在のmaxよりも大きければ、maxをcurrentAreaで更新する。 a++; そして、低い方のポインターであるaを右に1つ移動させる。

else { ... } 一方、もし右ポインターの線h[b]が左ポインターの線h[a]以下の場合（つまりh[b]の方が低いか、両者が同じ高さの場合）は、面積の高さはh[b]に制限される。 int currentArea=h[b]*(b-a); 同様に現在の面積currentAreaを計算する。この場合、高さは低い方のh[b]を使用する。 if(max<currentArea) max=currentArea; currentAreaがmaxよりも大きければmaxを更新する。 b--; そして、低い方（または同じ高さの場合）のポインターであるbを左に1つ移動させる。

このループがbがa以下になるまで（ポインターが交差するか、追い越すまで）繰り返され、すべての可能性が効率的に探索される。 return max; 最終的に、ループが終了したら、見つかった最大の面積maxを返す。

この問題の解決を通じて、効率的なアルゴリズム設計、特に2ポインターのようなテクニックを理解することは、システムエンジニアとして複雑な問題をスマートに解決するための重要なスキルとなる。