컨테이너 벽 높이의 배열이 제공됩니다. 목표는 최대 부피의 물을 담을 수 있는 용기를 찾는 것입니다. 벽의 높이는 배열의 요소이므로 벽 사이의 거리는 두 벽 사이의 너비로 간주됩니다. 예를 들어 높이 Arr[i]와 Arr[j]의 벽은 그 사이에 j-i 너비가 있습니다( 0<=i
따라서 물의 높이는 Arr[i]
우리는 그러한 최대 면적을 찾아야 합니다.
그림과 같이 벽 높이 5,1,2,3 및 벽 사이의 최대 너비는
최대 면적 컨테이너는 최대 물, 면적=20, 벽 Arr[0] 및 Arr[4]
최대 면적 컨테이너는 최대 물, 면적=16, 벽 Arr[0] 및 Arr[4]
정수 배열 wall[]은 벽의 높이를 포함합니다.
함수 mostwater(int A[], int len)는 높이의 배열과 숫자를 취합니다. 요소의 itand는 높이와 너비만 사용할 수 있으므로 대부분의 물이 있는 컨테이너의 영역을 반환합니다.
두 개의 인덱스 r=len-1 및 l=0을 사용하여 양쪽 끝에서 배열 탐색을 시작합니다.
정수 영역과 maxarea는 각각 현재 컨테이너의 영역과 지금까지 발견된 최대 컨테이너 영역을 저장하는 데 사용됩니다. 처음에는 0
int minwall,lwall,rwall 은 왼쪽 벽( A[l] ), 오른쪽 벽( A[r] )의 높이, lwall과 rwall의 최소 높이를 저장합니다.
( l
두 벽 사이의 너비는 지수의 차이( r-l )
물/용기의 면적을 minwall*( r-l )로 계산하고 면적을 업데이트합니다.
현재 영역이 최대인 경우 모든 벽에 대해 이 작업을 수행하십시오. 지금까지 최대 영역을 업데이트하십시오.
결국 maxarea는 대부분의 물이 담긴 컨테이너의 원하는 영역을 갖게 됩니다.입력
Arr[]= { 5,1,2,3,5 } 출력
Maximum water area : 20
설명
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
입력
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
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
예시
#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
