컨테이너 벽 높이의 배열이 제공됩니다. 목표는 최대 부피의 물을 담을 수 있는 용기를 찾는 것입니다. 벽의 높이는 배열의 요소이므로 벽 사이의 거리는 두 벽 사이의 너비로 간주됩니다. 예를 들어 높이 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]
를 갖습니다.아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 배열 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는 대부분의 물이 담긴 컨테이너의 원하는 영역을 갖게 됩니다.
- 결과적으로 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