Cho một mảng các số nguyên height có độ dài n. Tìm hai đường thẳng tạo thành bình chứa được lượng nước lớn nhất.
Ví dụ 1:
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49Định Dạng Đầu Vào (Input)
Một dòng chứa mảng các số nguyên height
Định Dạng Đầu Ra (Output)
Một số nguyên duy nhất là diện tích nước lớn nhất
Ràng Buộc (Constraints)
2 <= height.length <= 10^5
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[1, 8, 6, 2, 5, 4, 8, 3, 7]
Output:
49
Giải thích: Diện tích 7 * 7 = 49
Ví dụ 2:
Input:
[1, 1]
Output:
1
Giải thích: Diện tích 1 * 1 = 1
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Kỹ thuật Hai Con Trỏ Thu Hẹp O(n)
Hai con trỏ ở hai đầu. Tính diện tích min(h[l], h[r]) * (r - l). Cột nào thấp hơn thì dịch con trỏ bên đó vào trong.
Dữ liệu đầu vào (Input):
[1, 8, 6, 2, 5, 4, 8, 3, 7]
Kết quả kỳ vọng (Expected Output):
49
Dữ liệu đầu vào (Input):
[1, 1]
Kết quả kỳ vọng (Expected Output):
1
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
