資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究C++ 中盛最多水的容器
現有一個包含容器壁高度的陣列。目標是找出能夠容納最多水量的容器。由於壁的高度是陣列的元素，因此它們之間的距離被視為兩壁之間的寬度。例如，高度為 Arr[i] 和 Arr[j] 的壁之間的寬度為 j-i（0<=i<j<=N），其中 N 是壁的數量或陣列的長度。
所以水的高度將達到較低的高度，如果 Arr[i] < Arr[j]，水的高度將為 Arr[i]。寬度為 j-i，因此水的面積 = Arr[i] * ( j- 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) 接受高度陣列和陣列中的元素數量，並返回只有高度和寬度可用的盛最多水的容器的面積。
我們取兩個索引 r=len-1 和 l=0 從兩端開始遍歷陣列。
整數 area 和 maxarea 分別用於儲存當前容器的面積和迄今為止找到的最大容器面積。初始值為 0
int minwall、lwall、rwall 儲存左壁（A[l]）、右壁（A[r]）的高度以及 lwall 和 rwall 中最小的高度；
當 l<r 時，逐行遍歷陣列，對於每個 A[l] 和 A[r]，水的高度將是這兩個值中的較小值。將較小值儲存在 minwall 中
兩堵牆之間的寬度是索引的差值 ( 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
151 次瀏覽
