Container With Most Water

Q: Độ phức tạp thời gian của bài toán Container With Most Water là bao nhiêu?

Lời giải dùng hai con trỏ chạy trong thời gian O(n) và tốn O(1) bộ nhớ bổ sung, vì mỗi bước di chuyển một con trỏ vào trong một vị trí. Kiểm tra mọi cặp cần O(n²), còn sắp xếp các đường theo chiều cao cần O(n log n).

Q: Tại sao lại di chuyển con trỏ ở đường thẳng ngắn hơn?

Mực nước bị giới hạn bởi đường thẳng ngắn hơn. Mọi chiếc bình khác có đường thẳng đó đều có một đường thẳng đi kèm gần hơn, nên chiếc bình hẹp hơn và không cao hơn. Không chiếc bình nào trong số đó có thể chứa nhiều nước hơn chiếc bình bạn đã đo, vì vậy có thể bỏ qua đường thẳng ngắn hơn mà không làm mất đáp án.

Q: Container With Most Water có phải là một bài toán tham lam không?

Đúng vậy. Mỗi bước đưa ra một lựa chọn cục bộ và không bao giờ đảo ngược: bỏ đường thẳng ngắn hơn. Lựa chọn này an toàn vì mọi vùng chứa bị loại đều không tốt hơn vùng đã đo, đó là lý do bài toán này được xếp vào cả hai nhóm: tham lam và hai con trỏ.

Trung bìnhHai con trỏ Tham lam

+10

Bạn nhận được một danh sách height gồm các số nguyên không âm. Đường thẳng i là một bức tường thẳng đứng có chiều cao height[i], nằm tại vị trí i. Hai đường thẳng bất kỳ cùng với mặt đất tạo thành một vật chứa, có thể chứa lượng nước bằng chiều cao của đường thẳng thấp hơn nhân với khoảng cách giữa hai đường thẳng. Các đường thẳng khác không cản trở. Hãy trả về lượng nước lớn nhất mà một cặp đường thẳng có thể chứa.

Hàm

maxArea(height: integer-array) → integer

heightinteger-array: chiều cao của các đường tại vị trí 0, 1, 2, v.v.
Trả vềinteger: lượng nước tối đa mà hai dòng có thể chứa

Ràng buộc

2 ≤ height.length ≤ 10⁴
0 ≤ height[i] ≤ 10⁴
Đáp án tối đa là 10⁸, nên vừa với số nguyên (integer) 32 bit.

Ví dụ

Đầu vào: height = [3, 7, 2, 5, 4, 7, 3, 6]
Đầu ra: 36
Giải thích: Hai đường ở vị trí 1 và 7, có chiều cao lần lượt là 7 và 6, cách nhau 6 đơn vị và chứa được 6 × 6 = 36. Hai đường cao nhất, có chiều cao 7 ở vị trí 1 và 5, chỉ chứa được 7 × 4 = 28.

Câu hỏi mở rộng

Ở đây, các đường nằm giữa hai đường của bạn đều bị bỏ qua. Nếu mỗi đường đều là một thanh liền, sẽ có bao nhiêu nước đọng lại giữa tất cả chúng? Bạn cũng có thể tính điều đó trong O(n) không?

Lời giải

Kiểm tra tất cả n²/2 cặp sẽ cần 5 × 10^7 phép nhân với 10^4 đường thẳng. Lượng nước chỉ phụ thuộc vào đường thẳng ngắn hơn trong cặp, vì vậy khi một đường thẳng là cạnh ngắn hơn của chiếc bình rộng nhất mà nó có thể tạo thành, không chiếc bình nào hẹp hơn có cạnh đó có thể chứa nhiều nước hơn. Hai con trỏ biến việc này thành một lượt duyệt từ cả hai đầu.

Kiểm tra từng cặp

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Cặp i < j chứa min(height[i], height[j]) × (j - i): nước tràn qua bức tường thấp hơn, còn đáy rộng j - i. Thử mọi cặp và giữ lại giá trị lớn nhất.

n đường thẳng tạo thành n(n-1)/2 cặp: khoảng 5 × 10^7 cặp với 10^4 đường thẳng, và số cặp tăng gấp bốn lần mỗi khi n tăng gấp đôi.

Thuật toán

Đặt best thành 0.
Với mỗi i và mỗi j đứng sau nó, tính min(height[i], height[j]) × (j - i).
Giữ lại giá trị lớn hơn giữa best và giá trị đó.
Trả về best.

def maxArea(height):
    n = len(height)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            best = max(best, water)
    return best

Dòng cao nhất trước

Ý tưởng

Nếu đường thẳng ở vị trí i là cạnh ngắn hơn của một chiếc bình, cạnh còn lại có thể là bất kỳ đường thẳng nào cao ít nhất bằng nó. Vì vậy, chiếc bình tốt nhất sẽ ghép nó với đường thẳng xa nhất có chiều cao ít nhất bằng nó.

Sắp xếp các đường thẳng từ cao nhất đến thấp nhất. Khi đến lượt đường thẳng i, mọi đường thẳng đã xếp đều cao ít nhất bằng nó, và đường thẳng xa nhất là chỉ số đã xếp ở ngoài cùng bên trái hoặc bên phải, lo hoặc hi. Vì vậy, đường thẳng i có thể chứa nhiều nhất height[i] × max(i - lo, hi - i), và chiếc bình tốt nhất được tính khi cạnh ngắn hơn của nó đến lượt. Với hai đường thẳng có chiều cao bằng nhau, đường được xếp thứ hai xem đường đầu tiên là cạnh còn lại.

Trong ví dụ đầu tiên, hai đường thẳng cao 7 ở vị trí 1 và 5 được xét trước, chứa được 28. Sau đó, đường thẳng cao 6 ở vị trí 7 thấy lo = 1 và chứa được 36. Việc sắp xếp tốn O(n log n) thời gian và O(n) bộ nhớ.

Thuật toán

Sắp xếp các chỉ số theo chiều cao, từ cao nhất đến thấp nhất.
Đặt lo và hi bằng chỉ số đầu tiên trong thứ tự đó, và đặt best bằng 0.
Với mỗi chỉ số tiếp theo i, tính height[i] nhân với số lớn hơn giữa i - lo và hi - i, rồi giữ lại giá trị tốt nhất.
Cập nhật lo và hi để bao gồm i.
Trả về best.

def maxArea(height):
    # Indices from the tallest line to the shortest.
    order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
    lo = hi = order[0]  # leftmost and rightmost index among the lines placed so far
    best = 0
    for i in order[1:]:
        # Every placed line is at least as tall as line i, so line i is the
        # shorter side, and its best partner is the placed line farthest away.
        best = max(best, height[i] * max(i - lo, hi - i))
        lo = min(lo, i)
        hi = max(hi, i)
    return best

Hai con trỏ từ hai đầu

Ý tưởng

Bắt đầu với cặp đường thẳng cách xa nhau nhất, left = 0 và right = n-1, giả sử height[left] ≤ height[right]. Mọi cặp khác dùng đường thẳng left đều ghép nó với một đường thẳng gần hơn, nên khoảng cách hẹp hơn và chiều cao không vượt quá height[left]. Không cặp nào chứa được nhiều nước hơn lượng nước bạn đã đo, vậy đường thẳng left đã được xét xong và left dịch sang phải một bước. Nếu hai chiều cao bằng nhau thì cả hai đường thẳng đều đã được xét xong, nên dịch đường nào cũng được.

Mỗi bước loại bỏ một đường thẳng, nên hai con trỏ gặp nhau sau n-1 bước. Cặp tốt nhất không bao giờ bị bỏ qua: khi đường thẳng đầu tiên trong hai đường thẳng của cặp đó bị loại bỏ, lượng nước trong cặp được đo ở thời điểm ấy ít nhất cũng bằng lượng nước của cặp tốt nhất.

Ở ví dụ đầu tiên, các vị trí 0 và 7 chứa được 21 đơn vị nước, rồi đường thẳng có chiều cao 3 bị loại bỏ. Các vị trí 1 và 7 chứa được 36 đơn vị nước, rồi đường thẳng có chiều cao 6 bị loại bỏ. Các cặp còn lại chứa được 15, 28, 12, 10 và 2 đơn vị nước.

Thuật toán

Đặt left = 0, right = n-1 và best = 0.
Trong khi left < right, tính min(height[left], height[right]) × (right - left) và giữ lại giá trị lớn nhất.
Nếu height[left] < height[right], di chuyển left sang phải một bước. Nếu không, di chuyển right sang trái một bước.
Khi hai con trỏ gặp nhau, trả về best.

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        best = max(best, water)
        # The shorter line cannot do better with any line closer in, so drop it.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

Lỗi thường gặp và trường hợp biên

Di chuyển đường thẳng cao hơn. Ở ví dụ đầu tiên, kết quả là 21 thay vì 36: đường thẳng cao 6 ở vị trí 7 rời đi trước khi gặp đường thẳng cao 7 ở vị trí 1.
Dùng đường thẳng cao hơn hoặc chiều cao trung bình của hai đường thẳng. Nước tràn qua bức tường thấp hơn, vì vậy chiều cao là giá trị nhỏ hơn.
Tính chiều rộng bằng j - i + 1. Các đường thẳng ở vị trí i và j cách nhau j - i, vì vậy [4, 4] chứa được 4, không phải 8.
Cho rằng đáp án dùng các đường thẳng cao nhất hoặc cặp ngoài cùng. Ở ví dụ đầu tiên, hai đường thẳng cao 7 chứa được 28 và cặp ngoài cùng chứa được 21, trong khi đáp án là 36.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán Container With Most Water là bao nhiêu?

Lời giải dùng hai con trỏ chạy trong thời gian O(n) và tốn O(1) bộ nhớ bổ sung, vì mỗi bước di chuyển một con trỏ vào trong một vị trí. Kiểm tra mọi cặp cần O(n²), còn sắp xếp các đường theo chiều cao cần O(n log n).

Tại sao lại di chuyển con trỏ ở đường thẳng ngắn hơn?

Mực nước bị giới hạn bởi đường thẳng ngắn hơn. Mọi chiếc bình khác có đường thẳng đó đều có một đường thẳng đi kèm gần hơn, nên chiếc bình hẹp hơn và không cao hơn. Không chiếc bình nào trong số đó có thể chứa nhiều nước hơn chiếc bình bạn đã đo, vì vậy có thể bỏ qua đường thẳng ngắn hơn mà không làm mất đáp án.

Container With Most Water có phải là một bài toán tham lam không?

Đúng vậy. Mỗi bước đưa ra một lựa chọn cục bộ và không bao giờ đảo ngược: bỏ đường thẳng ngắn hơn. Lựa chọn này an toàn vì mọi vùng chứa bị loại đều không tốt hơn vùng đã đo, đó là lý do bài toán này được xếp vào cả hai nhóm: tham lam và hai con trỏ.

def maxArea(height):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

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

Đầu ra mong đợi

Container With Most Water

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Kiểm tra từng cặp

Dòng cao nhất trước

Hai con trỏ từ hai đầu

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự