塔の間で集められた水の量を見つける
1. 序章
このチュートリアルでは、プログラミングの課題を解決するための可能な方法を調査します。 さまざまな高さの一連の塔がある場合、それらの間の隙間に集めることができる水の最大量を見つけます。
さまざまな高さの一連の塔を考えると、水はそれらの間に、両側の最も高い塔の高さまで集まる可能性があります。 問題は、操作するタワーの任意のセットを指定して、この量を見つけることです。
たとえば、次のタワーのセットがあるとします。
14ユニットの水が収集されています。
- タワー1と3の間に2ユニット
- タワー3と8の間の11ユニット
- タワー8と10の間の1ユニット
2. ナイーブソリューション
素朴な解決策は、各タワーの上に集めることができる水の量を単純に数えることです。
最初と最後の塔の上に水を集めることはできません。 ここに集められる水は、タワーの外側から排出されます。 他のすべての塔の場合、水の量は、どちらかの側にある最も高い塔のどちらか短い方によって決定されます。
これは紛らわしい概念のように聞こえるので、それが何を意味するのかを理解します。 上記のタワーのセットでは、例としてタワー2を取り上げます。 ここに高さ3の塔があります。 左側には、高さ5の塔があります。 右側の塔の高さに関係なく、水は左側に流れ出るだけなので、レベル5を超えると水が溜まることはありません。
これを理解したので、アルゴリズムは次のようになります。
ここでは、2番目と最後から2番目の間のすべてのタワーを反復処理しています。 次に、これらのそれぞれについて、左側のすべてのタワー、次に右側のすべてのタワーを繰り返し処理して、各方向で最も高いタワーを見つけます。 次に、これら2つのセットのうち最短のものを使用します。 これを手に入れたら、私たちの水の量は、このタワーと私たちが作業しているタワーの違いになります。
これが完了したら、これらの数値を合計して、この一連のタワーの総水量を取得します。
2.1. 実行中のアルゴリズム
アルゴリズムを確認したので、それがどのように機能するかを見てみましょう。
タワー2から始まります。 まず、左側にあるすべてのタワーを調べて、どれが最も高いかを判断する必要があります –この場合、タワー1が唯一の選択肢です。 次に、右側のすべての塔を見て、どれが最も高いかを判断する必要があります –この場合、それは塔8です。
これらのうち、タワー1はタワー8よりも短いです。 最後に、これと私たちが作業しているタワーの高さの差は2ユニットです。タワーの高さは3で、タワー1の高さは5です。 これは、この塔の上に2ユニットの水を集めることができることを意味します。
次に、タワー3を見ていきます。 この場合、左側の最も高いタワーもタワー1であり、右側の最も高いタワーもタワー8です。 ただし、この場合、タワー3は両方よりも高いため、その上に水が溜まることはありません。
2.2. アルゴリズムコスト
このアルゴリズムは理解しやすいですが、非常に高価です。 10個のタワーのセットに対して、17個のループと88個の比較を実行しています。
特に、 2（t – 2）+1ループが必要です。 これは全体で1つのループであり、次に、表示しているすべてのタワーに2つのループが追加されます。これは、最初と最後を除く各タワーです。
次に、（t – 2）（t + 1）の比較も行う必要があります。 繰り返しますが、（t – 2）の部分は、最初と最後を除くすべてのタワーを調べているためです。 （t + 1）の部分は、実際には次のもので構成されています。
- 左右のすべてのタワーをその方向の現在の最大値と比較すると、これは常に t –1になります。
- これらのどれが最低の最大値であるかを計算するための追加の比較。
- これと現在の塔の高さの追加の比較。
これにより、（t + 1）と同じ（t – 1 + 1 + 1）が得られます。
3. 2つのパスでのソリューション
上記のソリューションは機能しますが、最適とは言えません。 私たちはこれよりもうまくやることができます。 事前にいくつかの詳細を検討することで、17を必要とせずに、タワーのリスト全体で2回のパスだけでまったく同じ計算を実行できます。
新しいタワーを見るたびに極大値を計算する代わりに、これらを計算して値を保存することができます。 これが可能なのは、タワーを適切な方向に横断するときに、極大値が下がることがないためです。
3.1. 実行中のアルゴリズム
前と同じように、このアルゴリズムの動作を見て、動作することを確認しましょう。
タワーのリスト全体で2つのパスを作成することで作業します。 最初のパスは、各タワーの番号のリストを作成し、このタワーの左側にある最も高いタワーを記録します。たとえば、タワー1と2は値5を記録し、タワー3から7は記録します。値が7の場合、タワー8から10は値9を記録します。
次に、逆を行い、右から左に通過して、これまでで最も高い塔を記録します。 各ステップで、以前に記録された左側の最も高い塔と、このパスで右から見た最も高い塔を使用して、この特定の塔の上の水の量を計算できます。
タワー10を見ると、左側が最も高いのは高さ9で、右側が最も高いのは高さ2です。 これは、この塔を高さ2と比較し、その上に水が集まっていないことを認識していることを意味します。
次に、タワー9を見てみましょう。 左側の最も高い塔はまだ高さ9で、右側の最も高い塔はまだ高さ2です。 ただし、この場合、現在のタワーの高さは1であるため、その上に1ユニットの水を集めています。
3.2. アルゴリズムコスト
今回は、タワーの数に関係なく、タワー全体で2回の反復を行うだけで済みます。 ただし、今回は 4t の比較を行います。左側のパスの各タワーに1つ、現在の最も高いパスを追跡するために右側のパスの各タワーに1つ、右側の各タワーにさらに2つです。それぞれの上の水の量を計算するためにパスします。
これを最初のアルゴリズムと比較すると、リストの6つのタワーに到達するとすぐにこれが安くなることがわかります。 これは、この場合のコストが線形であり、指数関数的ではないために発生します。
ただし、別のコストがかかります。 この場合、各タワーの追加データを追跡する必要があります。 それぞれの左側にある最も高い塔を追跡するための並列配列が必要です。 そのため、時間コストを大幅に改善することで、代わりにメモリ使用量で支払う必要がありました。
メンテナンスコストも高くなります。このアルゴリズムは理解が難しいため、コードの将来のメンテナンスに追加のコストがかかります。
4. 概要
ここでは、特定の問題、つまりタワー間で収集される水の量を計算する方法について説明しました。 次に、これに対するいくつかのソリューションを検討し、パフォーマンスとメンテナンスの複雑さの観点からそれらを比較しました。
アルゴリズムを可能な限り優れたものにするよう常に努力する必要がありますが、これを行うときはすべてを考慮する必要があります。 パフォーマンスを最適化したい場合があります。 また、代わりにメンテナンス用に最適化することをお勧めします。 この選択は、私たちが構築しているプロジェクトの正確な状況に常に依存します。
