Trapping Rain Water

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

---

Idea

• 找到数组的最高点，并讲数组分成左右两部分
• 左边部分：从左往右扫描，并设置变量记录左边的最大值leftPeak
• 每一条bar的水 ＝ 当前leftPeak - bar
• 右边部分同理，不同的是从右往左扫描

---

Solution

---

Special Case

• (4,2,3)