เราได้รับอาเรย์ความสูงของกำแพงภาชนะ เป้าหมายคือหาภาชนะที่จุน้ำได้มากที่สุด (ปริมาตรสูงสุด) ความสูงของน้ำถูกจำกัดโดยกำแพงที่ต่ำกว่า หาก 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] และ Arr[4] width=4, area = 5*4=20 Arr[1] และ Arr[4] width=3, area = 1*3=3 Arr[2] และ Arr[0] หรือ Arr[4] width=2, area = 2*2=4 Arr[3] และ Arr[0] width=3, area = 3*3=9 Arr[4] และ Arr[0] width=4, area = 5*4=20
ภาชนะจุน้ำมากที่สุด area=20 กำแพง Arr[0] และ Arr[4]
อินพุต
Arr[] = {1, 5, 4, 3, 2, 4}
เอาต์พุต
Maximum water area: 16
คำอธิบาย − พื้นที่สูงสุด 16 ที่กำแพง Arr[1] และ Arr[5] (ความสูง 4 และ 4, ความกว้าง 4)
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- อาเรย์ walls[] เก็บความสูงกำแพง
- ฟังก์ชัน mostwater(int A[], int len) คืนค่าพื้นที่สูงสุด
- ใช้ two pointers: l=0 (ซ้าย), r=len-1 (ขวา)
- ตัวแปร area, maxarea เก็บพื้นที่ปัจจุบันและสูงสุด
- minwall, lwall, rwall เก็บความสูงต่ำสุด, ซ้าย, ขวา
- while (l < r) คำนวณพื้นที่ = minwall * (r - l) อัปเดต maxarea
- ย้าย pointer ที่ความสูงต่ำกว่าเข้ามา (l++ หรือ r--)
- คืนค่า maxarea
ตัวอย่างโค้ด
#include <iostream>
using namespace std;
int mostwater(int A[], int len) {
int r = len - 1;
int l = 0;
int area = 0, maxarea = 0;
int minwall, lwall, rwall;
while (l < r) {
lwall = A[l];
rwall = A[r];
minwall = (lwall <= rwall) ? lwall : rwall;
area = minwall * (r - l);
maxarea = (area >= maxarea) ? area : maxarea;
if (lwall <= rwall)
l++;
else
r--;
}
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);
return 0;
}
ผลลัพธ์
Container with Most water has area: 16
