Container With Most Water

Bài toán

Cho một mảng height gồm n số nguyên. Mỗi phần tử là độ cao của một cột thẳng đứng. Tìm hai cột sao cho cùng với trục hoành (trục x), chúng tạo thành một "bể chứa" có thể đựng được nhiều nước nhất. Trả về lượng nước tối đa đó.

Công thức diện tích: $Area = (right - left) \times \min(height[left], height[right])$. (Chiều rộng nhân chiều cao thấp nhất của 2 cột).

Ví dụ:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Giải thích: Cột cao 8 (index 1) và cột cao 7 (index 8).
Khoảng cách = 8 - 1 = 7.
Chiều cao giới hạn = min(8, 7) = 7.
Area = 7 * 7 = 49.

Phân Tích & Tiếp Cận

Cách 1: Brute Force

Thử mọi cặp cột (i, j).

• Time Complexity: $O(n^2)$. Quá chậm.

Cách 2: Two Pointers (Greedy)

Ta muốn tối đa hóa Diện tích. Dễ thấy: Diện tích lớn nhất có tiềm năng nằm ở hai cột xa nhau nhất (chiều rộng lớn nhất).

1. Bắt đầu với left = 0, right = n - 1. Diện tích ban đầu có chiều rộng n-1.
2. Tính diện tích hiện tại.
3. Chiến thuật di chuyển:
   • Chiều cao của bể bị giới hạn bởi cột thấp hơn.
   • Nếu ta giữ nguyên cột thấp và di chuyển cột cao vào trong -> Chiều rộng giảm, chiều cao mới VẪN bị giới hạn bởi cột thấp cũ (hoặc thấp hơn nữa). => Diện tích chắc chắn giảm hoặc bằng. Vô ích!
   • Duy nhất cách để có cơ hội tăng diện tích: Từ bỏ cột thấp hiện tại và hy vọng tìm được cột cao hơn ở phía trong.

Quy tắc: "Luôn bỏ cột thấp hơn". (Nếu bằng nhau thì bỏ cột nào cũng được, hoặc bỏ cả 2).

function maxArea(height: number[]): number {
    let l = 0;
    let r = height.length - 1;
    let maxArea = 0;

    while (l < r) {
        // Tính diện tích hiện tại
        const currentArea = (r - l) * Math.min(height[l], height[r]);
        maxArea = Math.max(maxArea, currentArea);

        // Di chuyển con trỏ
        if (height[l] < height[r]) {
            l++; // Cột trái thấp hơn -> Dịch phải tìm cột cao hơn
        } else {
            r--; // Cột phải thấp hơn -> Dịch trái tìm cột cao hơn
        }
    }

    return maxArea;
}

• Time Complexity: $O(n)$ - Duyệt qua mảng đúng 1 lần.
• Space Complexity: $O(1)$.

Tư Duy "Greedy" (Tham lam)

Tại sao thuật toán này đúng? Bởi vì tại mỗi bước, ta loại bỏ một cột X (cột thấp hơn). Ta chứng minh được rằng cột X đó KHÔNG THỂ tạo ra diện tích lớn hơn với bất kỳ cột nào khác nằm ở phía trong vùng đang xét. Vì bất kỳ cặp nào gồm X và cột bên trong đều có:

• Chiều rộng < Chiều rộng hiện tại.
• Chiều cao $\le$ Chiều cao của X. => Diện tích chắc chắn nhỏ hơn hiện tại. => Việc loại bỏ X là an toàn.