Đề bài
Bars of width 1 have the given heights. After rain, water collects above each bar up to the lower of the tallest bars on its left and right. Compute the total trapped water. An O(n) two-pointer solution is expected.
Implement trapped_water(heights).
Input
heights: Bar heights from left to right.
Output
Return the total units of water.
Ràng buộc
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 100,000
Ví dụ
Ví dụ 1
Đầu vào:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Kết quả mong đợi:
expected = 6Đầu vào:
std::vector<long long> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Kết quả mong đợi:
long long expected = 6;Đầu vào:
long[] heights = new long[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Kết quả mong đợi:
long expected = 6;Giải thích
Water fills the dips: 1 + 1 + 2 + 1 + 1 = 6 units.
Ví dụ 2
Đầu vào:
heights = [3, 2, 1]
Kết quả mong đợi:
expected = 0Đầu vào:
std::vector<long long> heights = {3, 2, 1};
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long[] heights = new long[] {3, 2, 1};
Kết quả mong đợi:
long expected = 0;Giải thích
Heights only go down, so water runs off: 0.
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.