Garis yang lebih pendek membatasi air yang bisa ditampung container. Dari sini kita bisa melewati beberapa pasangan: pertahankan garis yang lebih tinggi, lalu geser sisi yang lebih pendek ke dalam.
Batasan luas
Input height berisi garis-garis vertikal. Garis i membentang dari (i, 0) ke (i, height[i]). Untuk dua index left dan right, lebar container adalah right - left, dan tingginya min(height[left], height[right]). Luasnya adalah hasil kali keduanya.
Baseline ini mengecek setiap pasangan garis:
function maxAreaNaive(height) {
let maxArea = 0;
// Check every possible pair
for (let i = 0; i < height.length - 1; i++) {
for (let j = i + 1; j < height.length; j++) {
let width = j - i;
let currentArea = Math.min(height[i], height[j]) * width;
maxArea = Math.max(maxArea, currentArea);
}
}
return maxArea;
}
Metode per pasangan ini benar, tapi butuh waktu O(n²). Dengan n sampai 10^5, pengecekan pasangan sebanyak itu terlalu mahal.
Aturan two pointer dan implementasinya
Mulai dari garis pertama dan terakhir, yang memberikan container paling lebar. Kalau height[left] lebih pendek, menggeser right bakal mengurangi lebar, sementara tinggi pembatasnya tetap sama atau malah lebih rendah. Langkah itu nggak mungkin menghasilkan luas yang lebih baik untuk garis kiri yang sekarang. Menggeser left adalah satu-satunya langkah yang mungkin menemukan garis pembatas yang lebih tinggi. Argumen yang sama berlaku kalau garis kanan yang lebih pendek.
function maxArea(height) {
let maxArea = 0;
let start = 0; // Left pointer
let end = height.length - 1; // Right pointer
while (start < end) {
let width = end - start;
// Area is limited by the shorter line
let currentArea = Math.min(height[start], height[end]) * width;
maxArea = Math.max(maxArea, currentArea);
// Move the pointer with the shorter line
if (height[start] <= height[end]) {
start++;
} else {
end--;
}
}
return maxArea;
}
// Driver Code
function main() {
let heightsArray = [1, 8, 6, 2, 5, 4, 8, 3, 7];
console.log("Input heights: ", heightsArray);
let result = maxArea(heightsArray);
console.log("Max water that can be contained: ", result);
}
main();
Invariant dan penelusuran
Setiap iterasi menghitung luas terbaik untuk pasangan saat ini, lalu membuang sisi yang membatasi luas itu. Untuk setiap pasangan yang dibuang, lebarnya nggak lebih besar dari lebar saat ini. Tingginya juga nggak lebih tinggi dari garis yang lebih pendek. Jadi, luasnya nggak mungkin melebihi luas yang udah dicek untuk sisi itu.
Untuk [1, 8, 6, 2, 5, 4, 8, 3, 7], tiga evaluasi pertamanya adalah:
- Mulai: left=0 (height=1), right=8 (height=7), area = min(1,7) × 8 = 8
- Geser left (lebih pendek): left=1 (height=8), right=8 (height=7), area = min(8,7) × 7 = 49
- Geser right (lebih pendek): left=1 (height=8), right=7 (height=3), area = min(8,3) × 6 = 18
- Lanjutkan sampai kedua pointer bertemu.
Luas maksimum yang ditemukan adalah 49.
Implementasi Java
class Solution {
public int maxArea(int[] height) {
int maxArea = 0;
int start = 0;
int end = height.length - 1;
while (start < end) {
int width = end - start;
maxArea = Math.max(maxArea, Math.min(height[start], height[end]) * width);
if (height[start] <= height[end]) {
start++;
} else {
end--;
}
}
return maxArea;
}
}
Kompleksitas dan aturan yang bisa dipakai ulang
Setiap pointer bergerak ke dalam paling banyak n kali. Scan ini butuh O(n) waktu dan O(1) extra space.
Garis yang lebih pendek itulah yang dilepas. Mempertahankannya sambil mengurangi lebar nggak bisa memperbesar luas, meskipun garis di sisi satunya lebih tinggi.

Memuat komentar...