Bài toán chứa nước mưa lớn nhất (Container With Most Water)
Cho mảng heights gồm N số nguyên không âm, mỗi phần tử biểu thị chiều cao của một cột thẳng đứng tại vị trí i. Hai cột bất kỳ cùng với trục hoành tạo thành một thùng chứa nước.
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: two pointers, arrays.
Nội dung đề bài
Mục tiêu kiến thức
- Nắm vững kỹ thuật hai con trỏ di chuyển từ hai phía biên vào trung tâm.
- Hiểu nguyên lý tham lam (Greedy Choice Property): dung tích bị giới hạn bởi cột ngắn hơn.
- Đạt độ phức tạp thời gian O(N) và bộ nhớ O(1).
Mô tả bài toán
Cho mảng heights gồm N số nguyên không âm, mỗi phần tử biểu thị chiều cao của một cột thẳng đứng tại vị trí i. Hai cột bất kỳ cùng với trục hoành tạo thành một thùng chứa nước.
Viết hàm max_water_area(heights: list[int]) -> int:
- Kiểm tra tính hợp lệ:
- Nếu N < 2, raise
ValueError("Can it nhat 2 cot de chua nuoc"). - Nếu tồn tại cột có chiều cao âm (< 0), raise
ValueError("Chieu cao cot khong duoc am"). - Diện tích nước chứa được giữa hai cột tại vị trí l và r (l < r) là:
Area = (r - l) × min(heights[l], heights[r])
- Tìm và trả về diện tích nước lớn nhất có thể chứa được.
Input
- Tham số:
heights: list[int].
Output
- Trả về:
int. - Ngoại lệ:
ValueErrorkhi N < 2 hoặc có chiều cao âm.
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.
Ví dụ 1
Input
max_water_area([1, 8, 6, 2, 5, 4, 8, 3, 7])Output
49Giải thích
Hàm được gọi với các tham số mẫu trên và trả về kết quả chính xác theo yêu cầu.
Ví dụ 2
Input
max_water_area([1, 1])Output
1Giải thích
Hàm được gọi với bộ tham số thứ hai và trả về kết quả tương ứng theo thiết kế.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.