Mã Nguồn Chi Tiết - top kiến tạo ngoại hạng anh 2025

Giới Thiệu Bài Toán

Chúng ta được cung cấp một dãy gồm n số nguyên không âm, đại diện cho chiều cao của các thanh dọc có độ rộng bằng 1. Nhiệm vụ là tính toán tổng lượng nước mưa có thể tích tụ giữa các thanh này sau khi trời mưa.

Ví Dụ

Với chiều cao = [0,1,0,2,1,0,1,3,2,1,2,1], kết quả đầu ra sẽ là: 6.
Giải thích: Hình ảnh trên minh họa cấu trúc chiều cao được biểu diễn bởi mảng [0,1,0,2,1,0,1,3,2,1,2,1]. Trong trường hợp này, tổng cộng có 6 đơn vị nước mưa (phần màu xanh lam) có thể tích tụ.

Phân Tích Đơn Giản

Ngay từ đầu, ý tưởng tự nhiên là quét từ trái sang phải để tìm các lịch bóng đá ngoại hạng anh "hố" chứa nước. Chẳng hạn như trong ví dụ, các hố nước đầu tiên và thứ hai đều có thể giải quyết theo cách này. Tuy nhiên, phương pháp này chỉ áp dụng tốt khi chiều cao bên phải lớn hơn hoặc bằng chiều cao bên trái. Nếu chiều cao bên trái lớn hơn mà bên phải thấp hơn thì cần thêm một bước xử lý khác. Có thể đảo ngược quá trình quét từ phải sang trái để đảm bảo tính toán chính xác hơn.

Dưới đây là đoạn mã ban đầu:

 1public int trap(int[] height) {
 2    int lastLeft = -1;
 3    int sum = 0;
 4    int tempSum = 0;
 5    boolean startFlag = true;
 6
 7    for (int j : height) {
 8        if (startFlag && j <= 0) {
 9            startFlag = false;
10            continue;
11        }
12        if (j >= lastLeft) {
13            sum += tempSum;
14            tempSum = 0;
15            lastLeft = j;
16        } else {
17            tempSum += lastLeft - j;
18        }
19    }
20    return sum;
21}

Tuy nhiên, sau khi tham khảo thêm các giải pháp trực tuyến, chúng ta nhận thấy rằng việc tìm kiếm giá trị tối đa bên trái và bên phải đối với mỗi ô riêng lẻ sẽ hiệu quả hơn. Ý tưởng cụ thể là: đối với mỗi cột, tìm giá trị tối đa ở phía trái và phía phải, chọn giá trị nhỏ hơn giữa hai giá trị đó, rồi trừ đi chiều cao hiện tại của cột. Kết quả chênh lệch này chính là lượng nước có thể tích tụ tại ô đó.

Mã Nguồn Chi Tiết

 1int n = height.length;
 2if (n <= 2) {
 3    return 0;
 4}
 5
 6// Sửa đổi thuật toán để tính toán lượng nước dựa trên từng ô riêng lẻ.
 7int maxL[] = new int[n];
 8int maxR[] = new int[n];
 9
10int max = height[0];
11maxL[0] = 0;
12
13// Tính toán giá trị tối đa bên trái cho từng cột.
14for (int i = 1; i < n - 1; i++) [Live Casino](/post/7aee9b0987602201.html)  {
15    maxL[i] = max;
16    if (max < height[i]) {
17        max = height[i];
18    }
19}
20
21max = height[n - 1];
22maxR[n - 1] = 0;
23
24int tempSum = 0, sum = 0;
25
26// Tính toán giá trị tối đa bên phải đồng thời tính tổng lượng nước.
27for (int i = n - 2; i > 0; i--) {
28    maxR[i] = max;
29    if (height[i] > max) {
30        max = height[i];
31    }
32
33    tempSum = Math.min(maxL[i], maxR[i]) - height[i];
34    if (tempSum > 0) {
35        sum += tempSum;
36    }
37}
38
39return sum;