- Công thức mực nước trên từng cột \(i\): Lượng nước đọng ngay phía trên cột \(i\) chỉ phụ thuộc vào cột cao nhất ở phía bên trái nó (\(L_{\max}(i) = \max_{0 \le j \le i} h[j]\)) và cột cao nhất ở phía bên phải nó (\(R_{\max}(i) = \max_{i \le j \lt n} h[j]\)) theo công thức: \(w[i] = \min(L_{\max}(i), R_{\max}(i)) - h[i]\).
- Bước đệm Quy hoạch động \(O(n)\) bộ nhớ: Tính trước hai mảng
pref_max[i]vàsuff_max[i]trong hai lượt quét thuận - ngược giúp giảm thời gian từ \(O(n^2)\) xuống \(O(n)\), nhưng tốn \(O(n)\) không gian lưu trữ phụ. - Tối ưu hóa Hai con trỏ \(O(1)\) bộ nhớ: Đặt
l = 0,r = n - 1và duy trìleft_max,right_max. Tại mỗi bước, nếuh[l] <= h[r], ta biết chắc chắn tường chắn bên phải ít nhất cao bằngh[r] >= left_max, nên mực nước tại cộtlbị quyết định hoàn toàn bởileft_maxmà không cần biết giá trị chính xác củaR_max(l). - Góc nhìn Ngăn xếp đơn điệu (Monotonic Stack): Thay vì cộng nước theo từng cột dọc, ngăn xếp giảm dần cho phép cộng nước theo từng lớp ngang mỗi khi gặp một cột cao hơn đáy thung lũng.
Phát biểu bài toán và công thức mực nước từng cột
Cho mảng số nguyên không âm height gồm \(n\) phần tử, trong đó height[i] biểu diễn chiều cao của cột địa hình thứ \(i\) (mỗi cột có bề rộng bằng \(1\) đơn vị). Hãy tính tổng lượng nước mưa có thể đọng lại giữa các cột sau cơn mưa.
Ví dụ với mảng kinh điển height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] (\(n = 12\)), tổng lượng nước đọng lại là \(6\) đơn vị.
Để giải bài toán này một cách hệ thống, câu hỏi đầu tiên cần đặt ra là: tại một cột chỉ số \(i\) cố định, nước trên đỉnh cột \(i\) có thể dâng cao tối đa tới mức nào mà không bị tràn ra hai biên?
Hãy tưởng tượng rót nước lên cột \(i\). Nước sẽ giữ lại được nếu cả phía bên trái (từ \(0\) đến \(i\)) và phía bên phải (từ \(i\) đến \(n - 1\)) đều có những bức tường cao hơn height[i]. Cụ thể:
- Gọi \(L_{\max}(i) = \max_{0 \le j \le i} \text{height}[j]\) là chiều cao lớn nhất từ đầu mảng tới cột \(i\).
- Gọi \(R_{\max}(i) = \max_{i \le j \lt n} \text{height}[j]\) là chiều cao lớn nhất từ cột \(i\) tới cuối mảng.
Theo nguyên lý bình thông nhau, mặt nước tại vị trí \(i\) sẽ bị giới hạn bởi bức tường thấp hơn trong hai bức tường chắn trái và chắn phải, tức là đạt độ cao tuyệt đối \(\min(L_{\max}(i), R_{\max}(i))\). Do bản thân cột đá tại vị trí \(i\) đã chiếm mất chiều cao \(\text{height}[i]\), lượng nước thực sự đọng phía trên cột \(i\) là:
\[\text{water}[i] = \min\big(L_{\max}(i),\; R_{\max}(i)\big) - \text{height}[i]\]
(Lưu ý: vì bản thân \(\text{height}[i]\) đã được tính trong cả \(L_{\max}(i)\) và \(R_{\max}(i)\), đại lượng \(\min(L_{\max}(i), R_{\max}(i))\) luôn lớn hơn hoặc bằng \(\text{height}[i]\), nên \(\text{water}[i] \ge 0\) với mọi \(i\)).
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] với tổng cộng \(6\) đơn vị nước mưa đọng lại tại các cột chỉ số \(2\) (\(+1\)), chỉ số \(4..6\) (\(+1, +2, +1\)) và chỉ số \(9\) (\(+1\)).Ba cấp độ tối ưu hóa trong phòng phỏng vấn
Cấp độ 1: Mảng cực đại tiền tố và hậu tố — Thời gian \(O(n)\), Bộ nhớ \(O(n)\)
Nếu ở mỗi cột \(i\), ta dùng vòng lặp quét sang trái để tìm \(L_{\max}(i)\) và quét sang phải để tìm \(R_{\max}(i)\), thuật toán vét cạn sẽ mất \(O(n^2)\) thời gian. Nhận thấy \(L_{\max}(i) = \max(L_{\max}(i - 1), \text{height}[i])\) và \(R_{\max}(i) = \max(R_{\max}(i + 1), \text{height}[i])\), ta có thể dùng kỹ thuật tương tự mảng cộng dồn để tính trước toàn bộ hai mảng L_max[0..n-1] và R_max[0..n-1] chỉ trong \(2\) lượt duyệt mảng, sau đó cộng tổng \(\min(L_{\max}[i], R_{\max}[i]) - \text{height}[i]\) ở lượt thứ ba.
Cách này cực kỳ dễ hiểu và đạt thời gian tuyến tính \(O(n)\), nhưng phải cấp phát thêm \(2\) mảng phụ kích thước \(n\). Ngay khi bạn trình bày xong cách này, người phỏng vấn sẽ hỏi câu tiếp theo: "Bạn có thể bỏ luôn hai mảng phụ đó để giải trong \(O(1)\) bộ nhớ không?"
Cấp độ 2: Hai con trỏ đối đầu — Thời gian \(O(n)\), Bộ nhớ phụ \(O(1)\)
Hãy quan sát kỹ công thức \(\min(L_{\max}(i), R_{\max}(i))\). Để tính giá trị nhỏ hơn giữa hai số \(A\) và \(B\), ta không cần biết giá trị chính xác của số lớn hơn — chỉ cần biết chắc chắn số nào nhỏ hơn là đủ!
Ta đặt con trỏ trái l = 0 ở đầu mảng, con trỏ phải r = n - 1 ở cuối mảng, cùng hai biến số nguyên:
left_max: giá trị lớn nhất trong đoạn đã quét từ bên trái \(\text{height}[0..l]\).right_max: giá trị lớn nhất trong đoạn đã quét từ bên phải \(\text{height}[r..n-1]\).
Tại mỗi bước khi \(l \le r\), ta so sánh height[l] và height[r]:
-
Trường hợp 1 (\(\text{height}[l] \le \text{height}[r]\)): Ta cập nhật
left_max = max(left_max, height[l]). Vì mọi phần tử trong \(\text{height}[0..l]\) đều từng được so sánh và nhỏ hơn hoặc bằng một phần tử nào đó ở đầu bên phải (hiện tại làheight[r]), ta luôn có bất biến:\[\text{left\_max} \le \text{height}[r] \le R_{\max}(l)\]
Nói cách khác, dù ở khoảng giữa \((l, r)\) có những cột cao bao nhiêu đi nữa, thì bức tường chắn toàn cục bên phải của cột \(l\) là \(R_{\max}(l)\) chắc chắn không thể thấp hơn
height[r], và do đó chắc chắn lớn hơn hoặc bằngleft_max. Suy ra:\[\min\big(L_{\max}(l),\; R_{\max}(l)\big) = \text{left\_max}\]
Nhờ vậy, ta chốt được ngay lượng nước đọng trên cột
llàleft_max - height[l]và dịch con trỏlsang phải (l++). -
Trường hợp 2 (
height[l] > height[r]): Hoàn toàn đối xứng, ta cập nhậtright_max = max(right_max, height[r]). Lúc này ở phía bên trái cộtrđã có sẵn cộtheight[l]cao hơnright_max, nên \(L_{\max}(r) \ge \text{height}[l] \ge \text{right\_max}\). Ta chốt ngay lượng nước trên cộtrlàright_max - height[r]và dịchrsang trái (r--).
Cấp độ 3: Ngăn xếp đơn điệu giảm dần (Cộng nước theo lớp ngang)
Ngoài hướng cộng nước theo từng cột dọc như hai con trỏ, bạn cũng nên biết cách dùng ngăn xếp đơn điệu giảm dần lưu chỉ số các cột. Khi duyệt tới cột \(i\) có \(\text{height}[i] \gt \text{height}[\text{st.top()}]\), cột ở đỉnh ngăn xếp đóng vai trò là đáy thung lũng mid = st.pop(). Cột mới ở đỉnh ngăn xếp sau khi pop là tường chắn trái left = st.top(), còn \(i\) là tường chắn phải. Lớp nước nằm ngang lấp đầy thung lũng này có chiều rộng \(W = i - \text{left} - 1\) và chiều cao \(H = \min(\text{height}[\text{left}], \text{height}[i]) - \text{height}[\text{mid}]\).
| Phương pháp | Thời gian | Bộ nhớ phụ | Cách gom lượng nước | Điểm mạnh trong phỏng vấn |
|---|---|---|---|---|
| Vét cạn từng cột | \(O(n^2)\) | \(O(1)\) | Theo cột dọc | Chỉ dùng để nêu định nghĩa cơ sở ban đầu. |
| Mảng tiền tố & hậu tố | \(O(n)\) | \(O(n)\) | Theo cột dọc (\(3\) lượt duyệt) | Trực quan nhất, dễ chuyển đổi sang 2 con trỏ. |
| Ngăn xếp đơn điệu | \(O(n)\) | \(O(n)\) | Theo lớp nước nằm ngang | Xử lý được luồng dữ liệu đến tuần tự từ trái sang phải. |
| Hai con trỏ đối đầu | \(O(n)\) | \(O(1)\) | Theo cột dọc (\(1\) lượt duyệt) | Lời giải tối ưu chuẩn cho mảng tĩnh 1 chiều. |
Ví dụ chạy tay từng bước với thuật toán Hai con trỏ
Ta chạy tay thuật toán hai con trỏ trên mảng height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] (\(n = 12\), chỉ số từ \(0\) đến \(11\)). Ban đầu l = 0, r = 11, left_max = 0, right_max = 0, total_water = 0.
| Bước | [l, r] |
h[l] vs h[r] |
Nhánh xử lý & cập nhật cực đại | Nước cộng thêm | Tổng nước | Con trỏ mới |
|---|---|---|---|---|---|---|
| 1 | [0, 11] |
0 <= 1 |
Xử lý l=0: left_max = max(0, 0) = 0 |
\(0 - 0 = 0\) | 0 |
l = 1, r = 11 |
| 2 | [1, 11] |
1 <= 1 |
Xử lý l=1: left_max = max(0, 1) = 1 |
\(1 - 1 = 0\) | 0 |
l = 2, r = 11 |
| 3 | [2, 11] |
0 <= 1 |
Xử lý l=2: left_max = max(1, 0) = 1 |
\(1 - 0 = \mathbf{1}\) | 1 |
l = 3, r = 11 |
| 4 | [3, 11] |
2 > 1 |
Xử lý r=11: right_max = max(0, 1) = 1 |
\(1 - 1 = 0\) | 1 |
l = 3, r = 10 |
| 5 | [3, 10] |
2 <= 2 |
Xử lý l=3: left_max = max(1, 2) = 2 |
\(2 - 2 = 0\) | 1 |
l = 4, r = 10 |
| 6 | [4, 10] |
1 <= 2 |
Xử lý l=4: left_max = max(2, 1) = 2 |
\(2 - 1 = \mathbf{1}\) | 2 |
l = 5, r = 10 |
| 7 | [5, 10] |
0 <= 2 |
Xử lý l=5: left_max = max(2, 0) = 2 |
\(2 - 0 = \mathbf{2}\) | 4 |
l = 6, r = 10 |
| 8 | [6, 10] |
1 <= 2 |
Xử lý l=6: left_max = max(2, 1) = 2 |
\(2 - 1 = \mathbf{1}\) | 5 |
l = 7, r = 10 |
| 9 | [7, 10] |
3 > 2 |
Xử lý r=10: right_max = max(1, 2) = 2 |
\(2 - 2 = 0\) | 5 |
l = 7, r = 9 |
| 10 | [7, 9] |
3 > 1 |
Xử lý r=9: right_max = max(2, 1) = 2 |
\(2 - 1 = \mathbf{1}\) | 6 |
l = 7, r = 8 |
| 11 | [7, 8] |
3 > 2 |
Xử lý r=8: right_max = max(2, 2) = 2 |
\(2 - 2 = 0\) | 6 |
l = 7, r = 7 |
| 12 | [7, 7] |
3 <= 3 |
Xử lý l=7: left_max = max(2, 3) = 3 |
\(3 - 3 = 0\) | 6 |
l = 8, r = 7 (Dừng) |
Bảng chạy tay cho thấy hai con trỏ l và r hội tụ đúng tại cột cao nhất của toàn mảng (i = 7, chiều cao bằng \(3\)) sau đúng \(12\) bước và trả về kết quả chính xác bằng \(6\).
Cài đặt bằng C++17, Python và Java 21
Chương trình dưới đây cài đặt lời giải hai con trỏ \(O(n)\) thời gian và \(O(1)\) bộ nhớ phụ theo cách viết thứ hai ở mục Hỏi đáp: khởi tạo left_max = height[0], right_max = height[n - 1], lặp khi l < r, so sánh left_max <= right_max rồi mới nhích con trỏ và cộng nước; kết quả luôn trùng với cách so sánh height[l] <= height[r] trong bảng chạy tay. Để tránh tràn số nguyên khi mảng địa hình có tới \(10^5\) cột và chiều cao mỗi cột lên tới \(10^9\) trong các biến thể thi đấu, biến tích lũy tổng lượng nước water được khai báo kiểu 64-bit (long long trong C++ và long trong Java).
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
long long trap_two_pointers(const vector<long long>& h) {
int n = (int)h.size();
if (n < 3) return 0;
int l = 0, r = n - 1;
long long left_max = h[0], right_max = h[n - 1];
long long water = 0;
while (l < r) {
if (left_max <= right_max) {
l++;
left_max = max(left_max, h[l]);
water += left_max - h[l];
} else {
r--;
right_max = max(right_max, h[r]);
water += right_max - h[r];
}
}
return water;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) {
vector<long long> sample = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
cout << trap_two_pointers(sample) << "\n";
return 0;
}
vector<long long> h(n);
for (int i = 0; i < n; i++) cin >> h[i];
cout << trap_two_pointers(h) << "\n";
return 0;
}
import sys
def trap_two_pointers(h: list[int]) -> int:
n = len(h)
if n < 3:
return 0
l, r = 0, n - 1
left_max, right_max = h[0], h[n - 1]
water = 0
while l < r:
if left_max <= right_max:
l += 1
if h[l] > left_max:
left_max = h[l]
water += left_max - h[l]
else:
r -= 1
if h[r] > right_max:
right_max = h[r]
water += right_max - h[r]
return water
def main():
tokens = sys.stdin.read().split()
if not tokens:
sample = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap_two_pointers(sample))
return
n = int(tokens[0])
h = [int(x) for x in tokens[1:1 + n]]
print(trap_two_pointers(h))
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
public static long trapTwoPointers(long[] h) {
int n = h.length;
if (n < 3) return 0;
int l = 0, r = n - 1;
long leftMax = h[0], rightMax = h[n - 1];
long water = 0;
while (l < r) {
if (leftMax <= rightMax) {
l++;
leftMax = Math.max(leftMax, h[l]);
water += leftMax - h[l];
} else {
r--;
rightMax = Math.max(rightMax, h[r]);
water += rightMax - h[r];
}
}
return water;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) {
long[] sample = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println(trapTwoPointers(sample));
return;
}
int n = sc.nextInt();
long[] h = new long[n];
for (int i = 0; i < n; i++) h[i] = sc.nextLong();
System.out.println(trapTwoPointers(h));
}
}
Các lỗi thường gặp và cách tự kiểm chứng
- Nhầm bài toán Hứng nước mưa (LeetCode 42) với Chứa nhiều nước nhất (Container With Most Water — LeetCode 11): Cả hai bài đều dùng hai con trỏ từ hai đầu mảng và cùng dịch chuyển bên có cột thấp hơn, nhưng bản chất vật lý khác hẳn nhau. Ở bài Container With Most Water, các cột chỉ là vách ngăn mỏng không chiếm thể tích và ta chỉ chọn một cặp cột duy nhất tạo thành thùng chứa diện tích \((r - l) \times \min(h[l], h[r])\). Ở bài Trapping Rain Water, mọi cột đều là khối đá đặc chiếm chỗ và ta tính tổng nước đọng ở mọi khe trũng trên toàn bộ địa hình.
- Cộng số âm vào tổng nước khi không cập nhật
left_maxtrước phép trừ: Nếu viếtwater += left_max - height[l]trước rồi mới gánleft_max = max(left_max, height[l]), khi gặp một cột mới cao hơnleft_maxcũ, hiệu sốleft_max - height[l]sẽ bị âm và làm giảm tổng nước! Cập nhậtleft_max = max(left_max, height[l])ngay đầu nhánhifđảm bảo hiệu số luôn không âm mà không cần viết thêm nhánhif(\(\text{height}[l] \lt \text{left\_max}\)). - Cách tự kiểm chứng tại nhà: Vì phương pháp mảng tiền tố - hậu tố (
min(L_max[i], R_max[i]) - height[i]) rất ngắn và gần như không thể viết sai, bạn hãy dùng chính hàm \(O(n)\) bộ nhớ đó làm chuẩn tham chiếu để so kết quả với hàm hai con trỏ \(O(1)\) bộ nhớ trên các ca biên: mảng chỉ có \(1\) hoặc \(2\) cột, mảng tăng dần hoàn toàn[1, 2, 3, 4], mảng giảm dần hoàn toàn[4, 3, 2, 1], mảng hình chữ V[5, 1, 5]và mảng hình chữ W có nhiều đỉnh bằng nhau[3, 0, 3, 0, 3].
Luyện ngay trên Big-O Coding
Để phân biệt rõ ràng các mẫu toán học trên biểu đồ cột (hai con trỏ đối đầu và ngăn xếp đơn điệu), bạn hãy thực hành ngay bộ ba bài toán kinh điển về biểu đồ cột trong lộ trình Coding Interview 150:
Trong thuật toán hai con trỏ, tại sao ta có thể so sánh \(\text{height}[l] \le \text{height}[r]\) thay vì so sánh \(\text{left\_max} \le \text{right\_max}\)?
Cả hai cách viết đều hoàn toàn đúng! Nếu viết điều kiện if (\(\text{left\_max} \le \text{right\_max}\)), bất biến càng hiển nhiên vì bạn đang so sánh trực tiếp hai bức tường chắn cao nhất đã biết ở hai đầu. Còn khi viết if (\(\text{height}[l] \le \text{height}[r]\)), do con trỏ chỉ nhích vào trong ở phía có cột thấp hơn, con trỏ đang đứng yên ở phía bên kia luôn giữ đúng vị trí của phần tử lớn nhất từng xuất hiện ở phía đó (tức là nếu l sắp di chuyển thì height[r] chính là right_max, hoặc trước đó đã có một cột bên phải còn cao hơn nữa). Vì thế hai điều kiện này tương đương nhau về mặt logic.
Nếu mở rộng bài toán lên lưới 2 chiều (Trapping Rain Water II — LeetCode 407), kỹ thuật hai con trỏ còn dùng được không?
Trên lưới 2 chiều kích thước \(m \times n\), nước tại một ô \((r, c)\) có thể thoát ra biên theo một đường đi ngoắt ngoéo bất kỳ trên mặt phẳng chứ không chỉ theo phương ngang hay phương dọc, nên kỹ thuật hai con trỏ hay giao của tiền tố 4 hướng đều bị sai. Để giải bài toán hứng nước mưa 2 chiều, ta phải tổng quát hóa tư duy "đi vào từ mép thấp nhất của hai con trỏ" thành thuật toán Dijkstra / Hàng đợi ưu tiên từ biên vào trong: đẩy toàn bộ các ô nằm trên 4 cạnh viền ngoài của ma trận vào một Min-Heap, sau đó liên tục rút ô có độ cao chắn thấp nhất \(H_{\min}\) ở đỉnh heap và lan vào các ô kề bên trong chưa thăm (nếu ô kề có chiều cao \(h \lt H_{\min}\) thì đọng được \(H_{\min} - h\) đơn vị nước và đẩy vào heap với độ cao chắn mới là \(\max(h, H_{\min})\)).
Khi nào người phỏng vấn muốn nghe lời giải Ngăn xếp đơn điệu thay vì Hai con trỏ?
Hai con trỏ yêu cầu toàn bộ mảng height[0..n-1] đã nằm sẵn trong bộ nhớ để có thể đọc phần tử cuối height[n - 1] ngay từ bước đầu tiên. Nếu người phỏng vấn đổi giả thiết thành luồng dữ liệu trực tuyến (streaming data) — các cột địa hình được gửi tới tuần tự từng cột một từ trái sang phải và bạn phải cập nhật lượng nước tích lũy ngay khi một thung lũng vừa khép kín bởi tường phải — thì bạn không thể đặt con trỏ ở cuối mảng được. Khi đó, ngăn xếp đơn điệu giảm dần là lựa chọn duy nhất xử lý được luồng dữ liệu một chiều từ trái qua phải.
Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.


