Phỏng vấn

Bài toán Hứng nước mưa (Trapping Rain Water): Từ Mảng tiền tố đến Hai con trỏ O(1)

Bài toán Hứng nước mưa (Trapping Rain Water — LeetCode 42) là một trong những câu hỏi phỏng vấn thuật toán mức độ Khó (Hard) nổi tiếng nhất vì một đề bài hình học trực quan lại mở ra tới ba hướng tiếp cận hoàn toàn khác nhau. Người phỏng vấn dùng bài toán này để quan sát cách ứng viên tiến hóa tư duy: bắt đầu từ công thức tính lượng nước đọng trên từng cột rời rạc, tối ưu hóa thời gian từ $O(n^2)$ xuống $O(n)$ bằng mảng cực đại tiền tố - hậu tố hoặc ngăn xếp đơn điệu, và cuối cùng rút gọn bộ nhớ phụ từ $O(n)$ xuống $O(1)$ bằng kỹ thuật hai con trỏ đối đầu. Bài viết này trình bày chi tiết từng bước chuyển tiếp và chứng minh chặt chẽ bất biến của lời giải hai con trỏ.

Ý chính
  • 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 - 1 và duy trì left_max, right_max. Tại mỗi bước, nếu h[l] <= h[r], ta biết chắc chắn tường chắn bên phải ít nhất cao bằng h[r] >= left_max, nên mực nước tại cột l bị quyết định hoàn toàn bởi left_max mà không cần biết giá trị chính xác của R_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\)).

Hứng nước mưa (Trapping Rain Water): height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Tổng lượng nước đọng = 1 + 1 + 2 + 1 + 1 = 6 đơn vị (Hai con trỏ L, R duy trì left_max và right_max) +1 +1 +2 +1 +1 i: 0 1 2 3 4 5 6 7 8 9 10 11 Nước tại cột i = max(0, min(left_max, right_max) - height[i]) Bất biến 2 con trỏ O(n), O(1) • Nếu height[L] <= height[R]: Chiều cao chặn tại L bị khóa bởi left_max (vì bên phải đã có cột height[R] >= left_max). • Ngược lại (height[L] > height[R]): Mực nước tại R quyết định bởi right_max, dịch R sang trái. Tổng nước = 6 đơn vị
Hứng nước mưa (Trapping Rain Water) height = [0,1,0,2,1,0,1,3,2,1,2,1] -> Tổng = 6 Nước đọng tại i=2 (+1), i=4..6 (+4), i=9 (+1) Quy tắc 2 con trỏ L và R (O(n) thời gian, O(1) bộ nhớ) • So sánh height[L] và height[R] ở mỗi bước. • Bên nào thấp hơn thì mực nước bị chặn bởi max của chính bên đó: cộng nước và nhích con trỏ vào.
Hình 1: Mặt cắt địa hình 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ằng left_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 l là left_max - height[l] và dịch con trỏ l sang phải (l++).

  • Trường hợp 2 (height[l] > height[r]): Hoàn toàn đối xứng, ta cập nhật right_max = max(right_max, height[r]). Lúc này ở phía bên trái cột r đã có sẵn cột height[l] cao hơn right_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ột r là right_max - height[r] và dịch r sang 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;
}

Các lỗi thường gặp và cách tự kiểm chứng

  1. 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.
  2. Cộng số âm vào tổng nước khi không cập nhật left_max trước phép trừ: Nếu viết water += left_max - height[l] trước rồi mới gán left_max = max(left_max, height[l]), khi gặp một cột mới cao hơn left_max cũ, hiệu số left_max - height[l] sẽ bị âm và làm giảm tổng nước! Cập nhật left_max = max(left_max, height[l]) ngay đầu nhánh if đảm bảo hiệu số luôn không âm mà không cần viết thêm nhánh if (\(\text{height}[l] \lt \text{left\_max}\)).
  3. 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.

Muốn học bài bản cùng giảng viên?

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.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483