数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
