[LeetCode] 42. Trapping Rain Water

轉自LeetCode

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.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

<Solution>

這題的想法如下

• 因為含水量，一定受限於最低高度，所以先準備兩個指針，一個從左一個從右，看看目前誰的高度比較小，然後再從小的那一方開始找起

• 確認比較小的高度在哪一邊後，舉例左邊，那從 left 指針開始往右找。而要能保存水，一定要遇到一個大於等於目前最低高度的地方，才可能存到水，而能存到水的量，就等於 minHeight - height[left]。從右邊找也是一樣的概念，方向不一樣而已

code 如下
c++

另一個是使用 stack 的概念來解(參考1, 參考2)

當遇到目前高度 <= stack的top 的時候，就放到 stack 裡面

因為當相鄰兩個高度是遞減的時候，是沒有空間可以儲水的

所以當遇到目前高度 > stack 的 top 的時候，代表找到一個凹朝可以存水

這時候將 stack 的 top 拿出來，然後左右邊界找比較低的那個，乘上距離算出儲水量

這邊要注意，如果將 top 拿出來後， stack 是空的時候

就代表相鄰兩個矩形是遞增的，且前面也沒有矩形了

也是沒辦法儲水，所以就繼續歷遍就好

kotlin