42. Trapping Rain Wate
Tags:
Hard
Skills:
Two pointer
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tính tổng lượng nước mưa có thể bị giữ lại giữa các cột có chiều cao khác nhau, được biểu diễn bằng một mảng số nguyên không âm. Để giải quyết, bạn cần xác định ở mỗi vị trí, lượng nước tối đa có thể giữ lại là bao nhiêu, sau đó cộng lại cho toàn bộ mảng
Approach
Các bước thực hiện
- Tạo hai mảng
max_leftvàmax_rightđể lưu chiều cao lớn nhất bên trái và bên phải cho từng vị trí - Duyệt từ trái sang phải để tính
max_left - Duyệt từ phải sang trái để tính
max_right - Tính tổng lượng nước giữ lại ở mỗi vị trí bằng công thức trên
Solution - Maintain 2 array
typescripttypescript
1function trap(height: number[]): number {
2 const n = height.length;
3 if(n < 3) return 0;
4
5 const left_max: number[] = new Array(n).fill(0);
6 const right_max: number[] = new Array(n).fill(0);
7
8 left_max[0] = height[0];
9 for(let i = 1; i < n; i++) {
10 left_max[i] = Math.max(left_max[i - 1], height[i]);
11 }
12
13 right_max[n - 1] = height[n - 1];
14 for(let i = n - 2; i >= 0; i--) {
15 right_max[i] = Math.max(right_max[i + 1], height[i]);
16 }
17
18 let total_water = 0;
19 for(let i = 0; i < n; i++) {
20 total_water += Math.min(left_max[i], right_max[i]) - height[i];
21 }
22
23 return total_water
24}Solution - two pointer
Phương pháp này sẽ dùng hai con trỏ đế tối ưu hóa việc tính toán:
- Dùng con trỏ left và right để duyệt từ hai đầu mảng
- Giữ hai biến left_max và right_max để lưu chiều cao lớn nhất ở hai phía
- Tại mỗi bước, nếu left_max < right_max, tính lượng nước tại con trỏ trái, ngược lại tính tại con trỏ phải
typescripttypescript
1function trap(height: number[]): number {
2 const n = height.length;
3 if (n < 3) return 0;
4
5 let left = 0;
6 let right = n - 1;
7 let left_max = 0;
8 let right_max = 0;
9 let total_water = 0;
10
11 while (left <= right) {
12 if (height[left] <= height[right]) {
13 if (height[left] >= left_max) {
14 left_max = height[left]
15 } else {
16 total_water += left_max - height[left];
17 }
18 left++
19 } else {
20 if (height[right] >= right_max) {
21 right_max = height[right]
22 } else {
23 total_water += right_max - height[right];
24 }
25 right--
26 }
27 }
28
29 return total_water
30}| Phương pháp | Độ phức tạp thời gian | Độ phức tạp không gian | Ưu điểm | Nhược điểm |
| Brute Force | O(n^2) | O(1) | Dễ hiểu | Chậm |
| Dynamic Programming | O(n) | O(n) | Nhanh hơn brute force | Tốn bộ nhớ |
| Two Pointers | O(n) | O(1) | Hiệu quả cả về thời gian lẫn bộ nhớ | Phức tạp hơn khi triển khai |
| Stack | O(n) | O(n) | Xử lý tốt trường hợp phức tạp | Tốn bộ nhớ hơn Two Pointers |
💡
Chỉ biết chiều cao hiện tại và chiều cao trước đó là chưa đủ để xác định lượng nước mưa giữ lại ở vị trí hiện tại
Vì sao không đủ
Giả sử bạn có mảng chiều cao như sau:
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Nếu chỉ nhìn vào chiều cao hiện tại và chiều cao trước đó, bạn sẽ bỏ lỡ trường hợp các “bức tường” cao hơn ở phía xa bên trái hoặc bên phải, có thể giữ nước ở các vị trí thấp hơn ở giữa
Ví dụ cụ thể:
- Ở vị trí thứ 2 (
height = 0), chiều cao trước đó là 1 (height = 1), nhưng phía bên phải lại có cột cao 2 (height = 2). Như vậy, vị trí này hoàn toàn có thể giữ nước, nhưng nếu chỉ xét chiều cao hiện tại và trước đó, bạn sẽ không phát hiện ra điều này.
Quy tắc tính nước mưa
Để xác định lượng nước ở vị trí i, bạn cần biết:
- Bức tường cao nhất bên trái (
maxLeft) - Bức tường cao nhất bên phải (
maxRight)
Nước giữ lại tại vị trí i là:
textwater[i] = min(maxLeft, maxRight) - height[i]
Nếu chỉ xét chiều cao hiện tại và trước đó, bạn không thể biết được maxRight (bức tường cao nhất bên phải).
Kết luận
- Không thể chỉ dùng chiều cao hiện tại và chiều cao trước đó để tính chính xác lượng nước giữ lại ở mỗi vị trí.
- Cần phải biết chiều cao lớn nhất ở cả hai phía (trái và phải) để xác định lượng nước giữ lại.