Bể Nước Tổng Công Ty Nước Sài Gòn

Mô tả

Anh Ba là kỹ sư của Tổng công ty Nước Sài Gòn, phụ trách giám sát hệ thống kênh dẫn giữa các trạm bơm. Để bảo vệ bờ bao, đội thi công đã xây dựng một dãy các bức tường bê tông vuông cạnh song song nhau, xếp sát mạch kề vỉa hè dọc theo một con kênh nhỏ ở ngoại thành. Cứ mỗi mét chiều dài ven kênh là một bức tường, và mỗi bức tường có độ cao tính bằng mét cho trước trong một dãy số nguyên. Khi trời đổ một cơn mưa cục bộ rất lớn, nước tràn ngập mặt đất và lấp đầy mọi khoảng trống giữa các bức tường. Nước dâng cao đến đâu thì bị các bức tường cao hơn chặn lại đến đó, phần vượt qua rào cản thấp nhất sẽ chảy tràn ra hai đầu con kênh và thoát xuống sông.

Nhiệm vụ của bạn là giúp anh Ba tính tổng lượng nước (tính bằng mét khối) bị mắc kẹt giữa các bức tường sau khi mưa ngừng lại và nước đã chảy ổn định. Mỗi đơn vị diện tích mặt đất rộng 1 mét và dài 1 mét được xem như một ô chứa được 1 mét khối nước.

Đầu vào

• Dãy số nguyên dương h gồm n phần tử, mỗi phần tử là chiều cao của một bức tường (đơn vị: mét).

Đầu ra

• Trả về một số nguyên duy nhất là tổng lượng nước đọng lại giữa các bức tường (đơn vị: mét khối).

Ràng buộc

• $1 \le n \le 10^5$
• $0 \le h[i] \le 10^4$
• Tổng lượng nước không vượt quá $10^9$.

Ví dụ

Ví dụ 1:

• Đầu vào: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
• Đầu ra: 6

Giải thích: Xét lần lượt các ô từ trái qua phải:

• Ô thứ 1 (chiều cao 0): không có tường bên trái nên không giữ được nước.
• Ô thứ 3 (chiều cao 0): tường cao nhất bên trái cao 1, bên phải cao 3, mực nước đạt $\min(1, 3) = 1$, đọng $1 - 0 = 1$ đơn vị.
• Ô thứ 5 (chiều cao 0): tường cao nhất bên trái cao 2, bên phải cao 3, mực nước đạt $\min(2, 3) = 2$, đọng đơn vị.

Ví dụ 2:

• Đầu vào: [4, 2, 0, 3, 2, 5]
• Đầu ra: 9