Pattern · Hai con trỏTrung bình
Bể Chứa Nước Nhiều NhấtContainer With Most Water
Hiểu bài
Cho mảng height gồm n số nguyên dương. Mỗi phần tử height[i] là chiều cao của đường thẳng đứng tại vị trí i. Tìm hai đường thẳng tạo thành bể chứa nhiều nước nhất cùng trục x.
Ví dụ:
ts
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
output = 49
// Đường i=1 (cao 8) và j=8 (cao 7): diện tích = min(8,7) × (8-1) = 7 × 7 = 49
height = [1, 1]
output = 1 // min(1,1) × (1-0) = 1Lượng nước chứa được = min(height[left], height[right]) × (right - left).
Không nghiêng bể — chỉ tính phần nằm ngang.
Cách cơ bản
O(n²) time, O(1) spacets
function maxArea(height: number[]): number {
let max = 0
for (let i = 0; i < height.length; i++) {
for (let j = i + 1; j < height.length; j++) {
const water = Math.min(height[i], height[j]) * (j - i)
max = Math.max(max, water)
}
}
return max
}Vì sao cách này chậm:
- Kiểm tra mọi cặp (i, j).
- Với n=10⁵ → 5·10⁹ cặp — quá chậm.
- Mẹo tối ưu: khi hai con trỏ tiến vào giữa, chiều rộng chỉ giảm dần → muốn diện tích lớn hơn buộc phải tăng chiều cao, mà chiều cao bị giới hạn bởi cột thấp hơn.
- Nhờ đó chỉ cần dịch cột thấp hơn vào trong và bỏ qua hàng loạt cặp vô ích → O(n).
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.