Cho n số nguyên không âm đại diện cho một bản đồ độ cao. Hãy tính lượng nước mưa có thể giữ lại giữa các cột.
Ví dụ 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6Định Dạng Đầu Vào (Input)
Một dòng chứa mảng số nguyên height
Định Dạng Đầu Ra (Output)
Một số nguyên duy nhất là lượng nước mưa tích trữ được
Ràng Buộc (Constraints)
1 <= height.length <= 2 * 10^4
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[0,1,0,2,1,0,1,3,2,1,2,1]
Output:
6
Giải thích: Đọng 6 đơn vị nước
Ví dụ 2:
Input:
[4,2,0,3,2,5]
Output:
9
Giải thích: Đọng 9 đơn vị nước
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ỏ O(n) Thời Gian & O(1) Bộ Nhớ
Duy trì leftMax và rightMax. Bên nào có cột thấp hơn thì lượng nước ở cột đó được xác định bởi max tương ứng trừ đi chiều cao cột.
Dữ liệu đầu vào (Input):
[0,1,0,2,1,0,1,3,2,1,2,1]
Kết quả kỳ vọng (Expected Output):
6
Dữ liệu đầu vào (Input):
[4,2,0,3,2,5]
Kết quả kỳ vọng (Expected Output):
9
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...
