Trapping Rain Water

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.

เงื่อนไข

0 ≤ length ≤ 200,000; 0 ≤ height ≤ 100,000

ตัวอย่าง

อินพุต:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

ผลลัพธ์ที่คาดหวัง:
expected = 6

อินพุต:
std::vector<long long> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

ผลลัพธ์ที่คาดหวัง:
long long expected = 6;

อินพุต:
long[] heights = new long[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

ผลลัพธ์ที่คาดหวัง:
long expected = 6;

อินพุต:
heights = [3, 2, 1]

ผลลัพธ์ที่คาดหวัง:
expected = 0

อินพุต:
std::vector<long long> heights = {3, 2, 1};

ผลลัพธ์ที่คาดหวัง:
long long expected = 0;

อินพุต:
long[] heights = new long[] {3, 2, 1};

ผลลัพธ์ที่คาดหวัง:
long expected = 0;

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

• From Problems to Performance: Two Decades of Programming Contests in the CCSC Southeast