C++で最も水が多いコンテナ

コンテナの壁の高さの配列が与えられます。目標は、最大量の水を入れることができる容器を見つけることです。壁の高さは配列の要素であるため、壁の間の距離は2つの壁の間の幅と見なされます。たとえば、高さArr[i]とArr[j]の壁の間にj-i幅があります（0 <=i

したがって、Arr [i]

そのような最大の領域を見つける必要があります。

入力

Arr[]= { 5,1,2,3,5 }

出力

Maximum water area : 20

説明

図に示すように、壁の高さが5、1、2、3の場合、壁間の最大幅は

Arr[0] and Arr[4] width=4, area = Arr[0]<=Arr[4] → 5*4=20
Arr[1] and Arr[4] width=3, area = Arr[1]<=Arr[4] → 1*4=4
Arr[2] and Arr[0] or Arr[4] width=4, area = Arr[0]<=Arr[0] → 2*2=4
Arr3] and Arr[0] width=3, area = Arr[0]<=Arr[0] → 3*3=9
Arr[4] and Arr[0] width=4, area = Arr[0]<=Arr[4] → 5*4=20

最大面積コンテナには、最大水、面積=20、壁Arr[0]およびArr[4]

入力

Arr[]= { 1, 5, 4, 3, 2, 4 }

出力

Maximum water area : 16

説明

Arr[0] and Arr[5] width=5, area = Arr[0]<=Arr[5] → 1*5= 5
Arr[1] and Arr[5] width=4, area = Arr[1]<=Arr[5] → 4*4=16
Arr[2] and Arr[5] width=3, area = Arr[2]<=Arr[5] → 3*4=12
Arr[3] and Arr[1] width=2, area = Arr[3]<=Arr[1] → 3*2=6
Arr[4] and Arr[1] width=3, area = Arr[1]<=Arr[4] → 2*3=6
Arr[5] and Arr[1] width=4, area = Arr[1]<=Arr[4] → 4*4=16

最大面積コンテナには、最大水、面積=16、壁Arr[0]およびArr[4]

以下のプログラムで使用されているアプローチは次のとおりです

• 整数配列walls[]には壁の高さが含まれています。

• 関数mostwater（int A []、int len）は、高さとnoの配列を取ります。高さと幅しか利用できないため、その中の要素の数と、ほとんどの水が入っているコンテナの領域を返します。

• 2つのインデックスr=len-1とl=0を使用して、両端から配列のトラバースを開始します。

• 整数のareaとmaxareaは、それぞれ現在のコンテナーの面積とこれまでに見つかったmaximumcontainerの面積を格納するために使用されます。最初は0

• int minwall、lwall、rwallは、左壁の高さ（A [l]）、右壁の高さ（A [r]）、およびlwallとrwallの最小の高さを格納します。

• （l

• 2つの壁の間の幅は、インデックスの差（r-l）

• 水/コンテナの面積をminwall*（r-l）として計算し、面積を更新します。

• 現在の面積がこれまでのところ最大である場合は、すべての壁に対してこれを行います。maxareaを更新します。

• 最終的に、maxareaには、ほとんどの水が入ったコンテナの目的の領域があります。

• 結果としてmaxareaを返します。

例

#include<iostream>
using namespace std;
int mostwater(int A[], int len){
   int r=len-1; //index of right wall of container
   int l=0; //index of left wall of container
   int area=0,maxarea=0;
   int minwall,lwall,rwall;
   // int area = 0;
   while (l < r){
      // Calculating the max area
      lwall = A[l]; //height of left wall of container
      rwall =A[r]; //height of right wall of container
      minwall=lwall<=rwall?lwall:rwall; //min. of two walls is height of water
      area=minwall*(r-l); // area is min wall* widht(r-l)
      maxarea=area>=maxarea?area:maxarea;
      if (l < r)
         l += 1;
      else
         r -= 1;
   }
   return maxarea;
}
int main(){
   int walls[] = {1, 5, 4, 3, 2, 4};
   int num = sizeof(walls) / sizeof(walls[0]);
   cout << endl <<"Container with Most water has area:"<< mostwater(walls,num);
}

出力

Container with Most water has area:16