Container With Most Water: tại sao luôn di chuyển cạnh ngắn hơn

Bước đi thì rõ ràng một khi có người chỉ cho bạn: đặt một pointer ở mỗi đầu, tính diện tích, trượt cạnh ngắn hơn vào trong, lặp lại. Hầu hết các giải thích dừng lại ở đó. Họ chỉ cho bạn xem code, khẳng định nó là O(n), rồi chuyển sang bài khác như thể phần khó là implementation chứ không phải là justification.

Nhưng code chỉ có ba dòng. Phần khó là tự thuyết phục bản thân — và có thể thuyết phục interviewer — rằng bạn sẽ không bao giờ bỏ lỡ cặp tối ưu khi thực hiện greedy move này. Đó mới là điều bài viết này thực sự nói đến.

Bài toán

Bạn có một mảng height gồm n số nguyên không âm. Mỗi số nguyên đại diện cho một đường thẳng đứng tại chỉ số đó. Chọn hai đường thẳng. Cùng với trục hoành, chúng tạo thành một container. Lượng nước container chứa được là:

area = (right - left) * min(height[left], height[right])

Chiều rộng là khoảng cách giữa hai đường thẳng. Chiều cao là đường thẳng nào ngắn hơn trong hai đường — vì đó là nơi nước tràn ra. Tìm cặp tối đa hoá diện tích này.

Ví dụ: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. Đáp án là 49, tạo bởi các đường thẳng tại index 1 (height 8) và index 8 (height 7): chiều rộng là 7, chiều cao là min(8, 7) = 7, diện tích là 49.

Constraints nói lên điều gì

n chạy đến 10^5. Điều đó loại O(n²) ngay lập tức — 10^10 operations vượt quá giới hạn thời gian khoảng bốn bậc độ lớn. Bạn cần gì đó tuyến tính hoặc gần đó.

Mỗi height[i] tối đa là 10^4. Vậy diện tích tối đa có thể là 10^5 * 10^4 = 10^9, hoàn toàn nằm trong phạm vi số nguyên 32-bit. Không cần lo về overflow.

Độ dài mảng tối thiểu là 2, có nghĩa là luôn tồn tại ít nhất một cặp hợp lệ. Không cần xử lý trường hợp mảng rỗng.

Những constraints này chỉ rõ hướng đi: O(n) time, O(1) space. Kết hợp đó, với bài toán mảng liên quan đến cặp phần tử, thường có nghĩa là two pointers.

Brute force: O(n²)

Trước khi tối ưu, hãy hiểu bạn đang tối ưu hoá cái gì. Mọi cặp (i, j) với i < j đều là candidate. Có n*(n-1)/2 cặp như vậy. Kiểm tra tất cả:

class Solution:
    def maxArea(self, height: list[int]) -> int:
        max_area = 0
        n = len(height)
        for i in range(n - 1):
            for j in range(i + 1, n):
                area = (j - i) * min(height[i], height[j])
                max_area = max(max_area, area)
        return max_area

public class Solution {
    public int MaxArea(int[] height) {
        int maxArea = 0;
        int n = height.Length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int area = (j - i) * Math.Min(height[i], height[j]);
                maxArea = Math.Max(maxArea, area);
            }
        }
        return maxArea;
    }
}

Đúng. Rõ ràng. Quá chậm với n = 10^5 — khoảng 5 * 10^9 phép tính cặp. Nhưng đáng để đọc vì nó làm rõ hình dạng của bài toán. Chúng ta đang tìm kiếm trong không gian hai chiều của các cặp (i, j). Cách tiếp cận two-pointer thu gọn điều đó thành một lần duyệt tuyến tính duy nhất. Câu hỏi là liệu bạn có thể làm vậy mà không bỏ sót cặp tối ưu hay không.

O(n²) time, O(1) space.

Lý luận greedy — đây là toàn bộ vấn đề

Đặt hai pointer: left = 0, right = n - 1. Đó là container rộng nhất có thể. Ghi lại diện tích của nó. Bây giờ bạn phải di chuyển một pointer vào trong — chiều rộng sẽ thu nhỏ bất kể bạn chọn cái nào. Biến số duy nhất bạn kiểm soát là điều gì xảy ra với chiều cao.

Giả sử height[left] < height[right]. Diện tích hiện tại là:

area = (right - left) * height[left]

vì đường thẳng bên trái ngắn hơn và giới hạn nước. Bây giờ hãy xem điều gì xảy ra nếu bạn di chuyển pointer phải thay vào đó:

• Chiều rộng giảm 1: (right - left) trở thành (right - left - 1).
• Ranh giới phải mới có chiều cao height[right'] nào đó. Dù nó có cao hơn right hiện tại, diện tích vẫn bị giới hạn bởi height[left] — đường thẳng ngắn hơn không di chuyển.
• Vậy diện tích mới là (right - left - 1) * min(height[left], height[right']), tối đa là (right - left - 1) * height[left].

Chiều rộng nhỏ hơn, cùng giới hạn, diện tích nhỏ hơn hoặc bằng. Mọi container bạn hình thành bằng cách di chuyển pointer phải — với pointer trái cụ thể này — đều tệ hơn hoặc bằng những gì bạn vừa tính. Bạn có thể loại bỏ tất cả chúng một cách an toàn.

Di chuyển cạnh ngắn hơn là lựa chọn hợp lý duy nhất. Không phải vì nó có thể tìm thấy thứ gì đó tốt hơn — có thể không — mà vì di chuyển cạnh cao hơn là vô dụng một cách có thể chứng minh được với cạnh ngắn hơn hiện tại.

Sơ đồ dưới đây cho thấy hai bước quyết định trên ví dụ điển hình:

Two pointers: O(n)

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0
        while left < right:
            area = (right - left) * min(height[left], height[right])
            max_area = max(max_area, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

public class Solution {
    public int MaxArea(int[] height) {
        int left = 0, right = height.Length - 1;
        int maxArea = 0;
        while (left < right) {
            int area = (right - left) * Math.Min(height[left], height[right]);
            maxArea = Math.Max(maxArea, area);
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return maxArea;
    }
}

O(n) time, O(1) space. Mỗi pointer di chuyển vào trong tối đa n lần tổng cộng; vòng lặp kết thúc khi chúng gặp nhau.

Trường hợp bằng nhau — height[left] == height[right] — rơi vào nhánh else và di chuyển pointer phải. Bạn có thể di chuyển cái nào cũng được. Khi cả hai đường thẳng có cùng chiều cao, chiều cao của container là giá trị đó bất kể bạn di chuyển pointer nào, và chiều rộng sẽ thu nhỏ đi 1 dù sao. Cả hai lựa chọn đều không bỏ qua đáp án tối ưu: cặp duy nhất với chiều rộng này và chiều cao này đã được ghi lại.

Trace ví dụ từng bước

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

Maximum 49 không bao giờ bị đe dọa sau bước 2. Pointer phải tiến lùi hết vì height[1] = 8 liên tục thống trị mọi thứ nó gặp, và không có đường thẳng nào ở giữa đủ cao để bù đắp cho chiều rộng đang thu hẹp.

Bước 4 đáng dừng lại xem xét. Cả hai pointer cùng rơi vào height 8, diện tích là 40 — không phải 49. Chiều rộng là 5, không phải 7. Nhánh else (tie) di chuyển right, hoàn toàn đúng: cặp đó đã bị đánh bại từ bước 2 và không thể phục hồi.

Tính đầy đủ: tại sao không có cặp nào bị bỏ qua

Lý luận trên xử lý một bước di chuyển. Nhưng sau nhiều bước di chuyển, khẳng định mạnh hơn: cách tiếp cận two-pointer xem xét mọi cặp có thể là tối ưu.

Chứng minh bằng invariant. Ở mỗi bước, tập hợp các cặp chúng ta đã loại bỏ chính xác là những cặp có cạnh ngắn hơn không thay đổi và chiều rộng nhỏ hơn. Chúng ta đã chứng minh rằng tất cả chúng đều bị cặp hiện tại thống trị. Bất kỳ cặp (i*, j*) nào là tối ưu, không pointer nào đã vượt qua nó khi pointer kia vẫn ở phía bên kia. Khi left = i* và right = j* — hoặc ngược lại — diện tích được tính toán và ghi lại. Vòng lặp không thể bỏ qua cấu hình này vì các pointer hội tụ từng bước một. Cặp tối ưu được đảm bảo sẽ được đánh giá.

Complexity

Solution two-pointer là asymptotically optimal cho bài toán này. Bạn không thể làm tốt hơn O(n) — bạn cần nhìn vào mọi phần tử ít nhất một lần để xác định rằng không có phần tử nào trong số chúng tạo thành container tối ưu.

Edge cases đáng chú ý

n = 2 là minimum. Vòng lặp chạy đúng một lần, tính diện tích duy nhất có thể, và trả về. Không cần xử lý đặc biệt — constraints đảm bảo điều này hoạt động.

Tất cả phần tử bằng nhau — height = [5, 5, 5, 5]. Diện tích bắt đầu ở 5 * 3 = 15 với container rộng nhất. Pointer phải di chuyển vào trong mỗi bước (trường hợp tie), và mỗi diện tích tiếp theo nhỏ hơn. Thuật toán trả về 5 * (n - 1), đúng: container rộng nhất thắng khi mọi chiều cao đều bằng nhau.

Một phần tử bằng 0 — height = [0, 8, 3, 0]. Bất kỳ container nào có đường thẳng chiều cao bằng 0 đóng góp diện tích bằng 0. Thuật toán xử lý đúng: min(height[left], height[right]) sẽ bằng 0 khi một trong hai biên là 0, nên những cấu hình đó đơn giản không thắng trong phép so sánh max. Pointer với height bằng 0 sẽ di chuyển vào trong ngay lập tức mỗi lần gặp.

Hai phần tử cả hai bằng 0 — height = [0, 0]. Cả hai đều bằng 0, diện tích là 0, vòng lặp chạy một lần và trả về 0. Nhánh else (tie) di chuyển right về index 0, vòng lặp thoát. Đúng.

Lỗi phổ biến nhất là dùng max thay vì min cho chiều cao. Nước đổ đầy đến đường thẳng ngắn hơn; trên đó nó tràn ra. Dùng max cho diện tích lớn hơn thực tế vật lý — sẽ fail ngay với height = [1, 100] vì đáp án đúng là 1 chứ không phải 100.

Vị trí của bài này trong series two-pointer

Bài này đến sau Two Sum II trong series, và nó giới thiệu điều gì đó mới: lý luận greedy. Việc di chuyển pointer của Two Sum II được thúc đẩy bởi tổng mục tiêu — nếu tổng quá nhỏ bạn cần giá trị lớn hơn, vì vậy bạn di chuyển left lên. Cơ học. Container With Most Water buộc bạn phải suy nghĩ kỹ hơn: di chuyển cạnh ngắn hơn không phải lúc nào cũng rõ ràng là đúng, và việc giải thích tại sao đòi hỏi lý luận loại bỏ ở trên.

Lý luận loại bỏ đó — "mọi cặp còn lại tiếp cận được bằng bước di chuyển này đều bị thống trị" — là mental model bạn mang theo. Nó xuất hiện lại trong Trapping Rain Water (42) và bất kỳ bài toán tìm cặp nào mà một biên giới hạn hàm mục tiêu.

Bài liên quan

Trapping Rain Water (42) là bài follow-up tự nhiên và nó khó hơn theo một cách cụ thể. Thay vì chọn hai đường ranh giới tự do, bạn đang tính lượng nước nằm trên mỗi phần tử dựa vào các phần tử lân cận. Ý tưởng two-pointer xuất hiện lại — bạn vẫn quan tâm đến phía ngắn hơn — nhưng bây giờ bạn tích luỹ nước ở tất cả các vị trí thay vì chỉ tính một hình chữ nhật. Lý luận greedy được truyền tiếp, nhưng kế toán phức tạp hơn. Hãy giải Container With Most Water cho đến khi lý luận loại bỏ cảm thấy tự nhiên; sau đó Trapping Rain Water sẽ có ý nghĩa hơn là cảm thấy như một loại bài hoàn toàn khác.

Two Sum II (167) dùng cùng kiểu hội tụ left-right pointer nhưng cho tổng mục tiêu trong mảng đã sắp xếp. Nếu sum < target, di chuyển left lên; nếu sum > target, di chuyển right xuống. Cấu trúc cơ học giống hệt nhau; thứ thay đổi là điều kiện điều khiển quyết định. Bài đó dễ hơn vì hướng di chuyển suy ra từ số học.

3Sum (15) mở rộng sang bộ ba phần tử. Bạn cố định một phần tử và chạy two pointers trên phần còn lại. Hiểu tại sao two-pointer hoạt động với cặp là điều kiện tiên quyết để hiểu tại sao phiên bản lồng nhau hoạt động với bộ ba.

Valid Palindrome (125) có cấu trúc tương tự — two pointers hội tụ từ hai đầu — nhưng điều kiện kết thúc và logic so sánh khác nhau. Đáng làm trước 3Sum để xây dựng thói quen hội tụ pointer mà không cần thêm sự phức tạp của lý luận greedy loại bỏ.