Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/trapping-rain-water/description/
Table of Contents
1. Cách tiếp cận vấn đề
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: Nhìn vào biểu đồ ở trên, ta thấy các khối block màu đen sẽ có chiều cao tương ứng với các giá trị tại mảng height, và trong trường hợp này, 6 ô màu xanh đại diện cho nước mưa đã được lấp đầy.
Nhiệm vụ của chúng ta vô cùng đơn giản và dễ hiểu 😉 chỉ cần đếm xem phần diện tích màu xanh mà biểu đồ có thể chứa là bao nhiêu.
1 điểm ta cần phải nhìn ra được để xác định được chiều cao của mực nước tại mỗi vị trí i đó chính là cần phải tồn tại 2 cạnh lần lượt bên trái và phải i có chiều cao lớn hơn hẳn chiều cao tại vị trí i, như vậy thì mới có đủ chỗ để chứa nước được. Và chiều cao mực nước sẽ bằng:
min(chiều cao lớn hơn bên trái i, chiều cao lớn hơn bên phải i) - chiều cao tại i
Và 2 chiều cao ta cần tìm tạm gọi là biên trái và biên phải tạm gọi là maxLeft và maxRight sẽ được duy trì với mỗi lần ta duyệt qua 1 block mới, ví dụ:
2. Solution & Phân Tích
Ta sẽ sử dụng kỹ thuật 2 Pointers với left pointer giữ index 0 và right pointer giữ index n - 1 với n là số lượng các block. Như vậy ta sẽ chắc chắn duyệt qua được hết các block vì điều kiện dừng sẽ là khi left >= right. Vậy câu hỏi đặt ra là khi nào chúng ta sẽ tăng left, khi nào sẽ giảm right, và làm sao để tính xem chiều cao lượng nước mà block đó có thể chứa là bao nhiêu?
Như đã đề cập từ trước, ta cần duy trì 2 giá trị maxLeft (giá trị max hiện tại tính từ left) và maxRight (giá trị max hiện tại tính từ right) để đảm bảo mỗi khi duyệt qua từng phần tử, ta luôn có 2 biên trái và phải đều có chiều cao lớn hơn nó để tính chiều cao của lượng nước. Ta sẽ duyệt qua từng phần tử bằng việc tăng left hoặc giảm right pointer:
- Nếu maxLeft <= maxRight -> Ta cần tăng left để tìm ra giá trị mới cho maxLeft:
- Nếu height[left] >= maxLeft -> Cập nhật lại giá trị của maxLeft và lượng nước có thể chứa lúc này = maxLeft - height[left] = 0 vì vị trí tại left chính là biên trái.
- Nếu height[left] < maxLeft mà maxLeft <= maxRight ->Chiều cao của lượng nước có thể chứa tại vị trí left chính là = min(maxLeft, maxRight) - height[left] = maxLeft - height[left].
- Như vậy ta sẽ cộng kết quả của maxLeft - height[left] vào biến tổng lượng mưa sau cùng.
- Nếu maxLeft > maxRight -> Ta cần giảm right để tìm ra giá trị mới cho maxRight:
- Nếu height[right] >= maxRight -> Cập nhật lại giá trị của maxRight và lượng nước có thể chứa lúc này = maxRight - height[right] = 0 vì vị trí tại right chính là biên phải.
- Nếu height[right] < maxRight mà maxLeft > maxRight -> Chiều cao của lượng nước có thể chứa tại vị trí left chính là = min(maxLeft, maxRight) - height[right] = maxRight - height[right].
- Như vậy ta sẽ cộng kết quả của maxRight - height[right] vào biến tổng lượng mưa sau cùng.
Tại sao cần phải tăng left hoặc giảm right trước rồi mới cập nhật giá trị cho maxLeft, maxRight và tính toán lượng nước? Lý do đơn giản vì ban đầu ta đặt 2 pointer ở 2 block rìa trái và phải cũng đang chính là maxLeft và maxRight, nên 2 block này cũng sẽ không thể chứa được lượng nước nào và ta cần tăng left hoặc giảm right để có thể tính toán lượng nước theo yêu cầu. Và ta sẽ tăng left cho đến khi tìm được giá trị maxLeft mới > maxRight, cũng như giảm right cho đến khi tìm được giá trị maxRight mới >= maxLeft.
Time-Complexity: O(n)
Space-Complexity: O(1)
Với n là số lượng các block.
3. Code
