Trapping Rain Water

Q: Độ phức tạp thời gian của bài toán Trapping Rain Water là gì?

Lời giải dùng hai con trỏ chạy trong thời gian O(n) và dùng thêm O(1) không gian, vì mỗi bước di chuyển một con trỏ vào phía trong. Phiên bản dùng mảng leftMax và rightMax cũng chạy trong thời gian O(n) nhưng dùng O(n) không gian. Quét cả hai phía từ mỗi thanh có độ phức tạp O(n²) .

Q: Có thể giải bài toán hứng nước mưa bằng ngăn xếp không?

Đúng. Hãy giữ một ngăn xếp các chỉ số có chiều cao giảm dần. Khi gặp một thanh cao hơn, hãy lấy phần tử trên cùng ra: đó là đáy của vùng nước được chắn bởi thanh mới trên cùng và thanh hiện tại. Cộng thêm (min(two walls) - floor) × (distance between the walls - 1) rồi tiếp tục lấy phần tử ra. Cách này lấp nước theo từng lớp ngang, với thời gian và không gian O(n) .

Q: Trapping Rain Water khác Container With Most Water như thế nào?

Trong bài Container With Most Water, các đường thẳng không chiếm diện tích, và đáp án là hình chữ nhật lớn nhất duy nhất nằm giữa hai đường. Ở đây, mỗi cột đều đặc, và đáp án là tổng lượng nước trên tất cả các cột. Cả hai đều di chuyển cạnh thấp hơn vì cùng một lý do: kết quả của cạnh đó đã được xác định.

KhóHai con trỏ Ngăn xếp đơn điệu

+10

Một hàng thanh đứng cạnh nhau, mỗi thanh rộng một đơn vị: height[i] là chiều cao của thanh i. Nước mưa đọng lại ở những chỗ trũng giữa các thanh. Nước chỉ đọng phía trên một thanh nếu có một thanh cao hơn ở đâu đó bên trái và một thanh cao hơn ở đâu đó bên phải thanh đó; nước sẽ chảy đi ở phía ngoài thanh đầu tiên và thanh cuối cùng. Hãy trả về tổng số đơn vị nước mà hàng thanh này giữ lại.

Hàm

trap(height: integer-array) → integer

heightinteger-array: chiều cao của từng thanh, từ trái sang phải
Trả vềinteger: tổng số đơn vị nước bị giữ lại

Ràng buộc

1 ≤ height.length ≤ 2 × 10⁴
0 ≤ height[i] ≤ 10⁵
Mỗi thanh rộng một đơn vị, và nước không đọng lại bên ngoài thanh đầu tiên hoặc thanh cuối cùng.

Ví dụ

Đầu vào: height = [0, 3, 1, 0, 2, 5, 1, 2]
Đầu ra: 7
Giải thích: Giữa 3 và 5, mức là 3: cách 2 đơn vị so với 1, 3 đơn vị so với 0 và 1 đơn vị so với 2. Số 1 phía sau nằm giữa 5 và 2, nên giữ nguyên giá trị 1. Vậy kết quả là 7.

Câu hỏi mở rộng

Giả sử các thanh tạo thành một lưới 2D với các độ cao và nước có thể thoát ra theo cả bốn hướng. Khi đó, bạn sẽ đếm lượng nước bị giữ lại như thế nào?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Lượng nước phía trên một thanh phụ thuộc vào các thanh có thể nằm rất xa ở cả hai phía. Mực nước là giá trị nhỏ hơn giữa thanh cao nhất bên trái và thanh cao nhất bên phải, còn lượng nước thanh đó giữ lại bằng mực nước trừ đi chiều cao của chính nó. Các cách tiếp cận chỉ khác nhau ở cách tìm hai giá trị lớn nhất đó.

Quét cả hai mặt từ mỗi thanh

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

Ý tưởng

Với mỗi thanh i, quét từ 0 đến i để tìm thanh cao nhất ở bên trái, rồi quét từ i đến cuối để tìm thanh cao nhất ở bên phải, sau đó cộng min(leftMax, rightMax) - height[i]. Đưa thanh i vào cả hai lần quét để lượng nước không bị âm và các thanh ở hai đầu có giá trị 0.

Mỗi thanh quét toàn bộ hàng: n = 2 × 10^4 nghĩa là có 4 × 10^8 lượt đọc, phần lớn lặp lại lần quét của thanh ngay trước đó.

Thuật toán

Gán water bằng 0.
Với mỗi chỉ số i, quét từ 0 đến i để tìm leftMax.
Quét từ i đến chỉ số cuối cùng để tìm rightMax.
Cộng min(leftMax, rightMax) - height[i] vào water.
Trả về water.

def trap(height):
    n = len(height)
    water = 0
    for i in range(n):
        # The tallest bar at or left of i, and the tallest at or right of i.
        left_max = 0
        for j in range(i + 1):
            left_max = max(left_max, height[j])
        right_max = 0
        for j in range(i, n):
            right_max = max(right_max, height[j])
        water += min(left_max, right_max) - height[i]
    return water

Tính trước thanh cao nhất ở mỗi bên

Ý tưởng

Cột cao nhất từ 0 đến i là cột cao hơn giữa cột cao nhất từ 0 đến i-1 và height[i]. Vì vậy, một lượt duyệt từ trái sang phải điền leftMax, mỗi phần tử được tính từ phần tử trước đó, còn một lượt duyệt từ phải sang trái điền rightMax. Lượt duyệt thứ ba áp dụng công thức.

Với [0, 3, 1, 0, 2, 5, 1, 2], các mức min(leftMax[i], rightMax[i]) là [0, 3, 3, 3, 3, 5, 2, 2]. Lấy các chiều cao trừ khỏi đó, ta được [0, 0, 2, 3, 1, 0, 1, 0], tổng cộng là 7. Thời gian chạy là O(n), đổi lại cần hai mảng gồm n số.

Thuật toán

Điền leftMax từ trái sang phải: leftMax[0] = height[0], sau đó leftMax[i] = max(leftMax[i-1], height[i]).
Điền rightMax từ phải sang trái: rightMax[n-1] = height[n-1], sau đó rightMax[i] = max(rightMax[i+1], height[i]).
Với mỗi chỉ số, cộng min(leftMax[i], rightMax[i]) - height[i] vào tổng.
Trả về tổng.

def trap(height):
    n = len(height)
    left_max = [0] * n   # tallest bar from index 0 to i
    right_max = [0] * n  # tallest bar from index i to n-1
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    return water

Hai con trỏ di chuyển về phía cạnh thấp hơn

Ý tưởng

Công thức chỉ cần bức tường thấp hơn, và hai con trỏ có thể xác định bức tường đó. Đặt left ở vị trí 0 và right ở chỉ số cuối cùng, theo dõi leftMax và rightMax, là thanh cao nhất mà mỗi con trỏ đã đi qua, tính cả thanh tại vị trí của chính nó, rồi luôn di chuyển con trỏ ở thanh thấp hơn. Khi đó, mọi thanh đã đi qua đều không cao hơn thanh cao hơn trong hai thanh hiện tại, vì một con trỏ chỉ bước qua một thanh không cao hơn thanh nằm dưới con trỏ còn lại.

Giả sử height[left] < height[right]. Theo bất biến, leftMax không vượt quá height[right], một thanh nằm bên phải left. Vì vậy, bức tường bên phải của left cao ít nhất bằng leftMax, và mực nước tại đó chính xác là leftMax, bất kể có gì nằm giữa hai con trỏ. Khi thanh bên phải thấp hơn hoặc bằng, lập luận tương tự sẽ giải quyết right.

Thuật toán

Đặt left = 0, right = n-1, và đặt leftMax, rightMax cùng water bằng 0.
Khi left < right: nếu height[left] < height[right], tăng leftMax lên bằng height[left] nếu cần, cộng thêm leftMax - height[left] vào lượng nước rồi dịch left sang phải.
Nếu không, làm tương tự ở phía bên phải rồi dịch right sang trái.
Trả về water. Thanh mà hai con trỏ gặp nhau là thanh cao nhất và không giữ nước.

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0  # tallest bar passed so far from each end
    water = 0
    while left < right:
        if height[left] < height[right]:
            # A bar taller than height[left] waits on the right, so left_max sets the level here.
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            # A bar at least as tall as height[right] waits on the left, so right_max sets the level.
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

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

Cộng lượng nước trước khi cập nhật mức cao nhất đã gặp. Khi height[left] cao hơn leftMax, lượng nước là số âm và tổng giảm xuống.
Di chuyển con trỏ ở thanh cao hơn, dù chưa chứng minh được mức của thanh đó. Với [4, 1, 3, 0, 5], phiên bản đó trả về 4 thay vì 8.
Chỉ xét các thanh liền kề. Trong [3, 0, 2, 0, 1, 0, 4], thanh có độ cao 1 chứa nước đến mức 3, được xác định bởi các thanh cách đó bốn và hai bước; đáp án là 12.
Coi hai đầu mảng là tường. Nước tràn ra ngoài ở đó, vì vậy một thanh, hai thanh hoặc một hàng chỉ tăng hay chỉ giảm đều chứa 0 nước.

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

Độ phức tạp thời gian của bài toán Trapping Rain Water là gì?

Lời giải dùng hai con trỏ chạy trong thời gian O(n) và dùng thêm O(1) không gian, vì mỗi bước di chuyển một con trỏ vào phía trong. Phiên bản dùng mảng leftMax và rightMax cũng chạy trong thời gian O(n) nhưng dùng O(n) không gian. Quét cả hai phía từ mỗi thanh có độ phức tạp O(n²).

Có thể giải bài toán hứng nước mưa bằng ngăn xếp không?

Đúng. Hãy giữ một ngăn xếp các chỉ số có chiều cao giảm dần. Khi gặp một thanh cao hơn, hãy lấy phần tử trên cùng ra: đó là đáy của vùng nước được chắn bởi thanh mới trên cùng và thanh hiện tại. Cộng thêm (min(two walls) - floor) × (distance between the walls - 1) rồi tiếp tục lấy phần tử ra. Cách này lấp nước theo từng lớp ngang, với thời gian và không gian O(n).

Trapping Rain Water khác Container With Most Water như thế nào?

Trong bài Container With Most Water, các đường thẳng không chiếm diện tích, và đáp án là hình chữ nhật lớn nhất duy nhất nằm giữa hai đường. Ở đây, mỗi cột đều đặc, và đáp án là tổng lượng nước trên tất cả các cột. Cả hai đều di chuyển cạnh thấp hơn vì cùng một lý do: kết quả của cạnh đó đã được xác định.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

height = [0, 3, 1, 0, 2, 5, 1, 2]

Đầu ra mong đợi

Trapping Rain Water

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Quét cả hai mặt từ mỗi thanh

Tính trước thanh cao nhất ở mỗi bên

Hai con trỏ di chuyển về phía cạnh thấp hơn

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ự