[063] LeetCode 42 演算法【Trapping Rain Water】收集雨水

42. Trapping Rain Water (Hard)

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.

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!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

這題有三種解法，雙指針、Stack、DP，相信有跟著我文章的朋友應該依看到這題目就可以想到能用DP去處理，我們先講雙指針的部分。

1.雙指針

這題思路很簡單，我們現在我們開兩個指針去做，左右兩邊我們先抓出兩邊最高的那一個地方，抓到以後指針往中間移動，只移動低的指針，接下來移動過程中我們判斷當下的地區可能有幾種情況：

1.跟原本的指針一樣高
2.比原本指針低
3.比原本指針高

計算水的公式為找出兩邊最低點並以(某一邊最高－某一邊目前高度)，因為水位是要用某邊最高高度去算，我們直接看代碼：

2.Stack

如果仔細看圖的話可以看出規律，藍色水外面一定是黑色的牆壁，這就剛好符合Stack這個資料結構，我們IDE的語法器就是用Stack去判斷的，判斷是否有把誇號打完就是利用Stack這個資料結構。

我們今天要做的事情很簡單：

1.丟入牆壁高度的index
2.如果比棧內前一個值低的話入棧，空棧的話結束
3.假設比前一個高的話，出棧並獲取當前棧頂元素(棧頂元素為低處會裝水)
4.比對獲取的棧頂跟當前的棧差多少，並且乘以距離(當前-棧頂-1)
5.指針往後移動

3.DP

動態規劃的前提就是最佳子結構，無後效性，然後想辦法把上一次結果存起來，以我們這題來看的話，其實可以直接關注水滴左右兩旁的柱子高度就可以，最低柱子高度乘以比最低柱子高度更低的長度就會是水滴長度，有點繞口，我們可以使用兩個Array先記錄起從左邊開始看的高度成長以及從後邊開始看的高度成長，接下來我們再去取兩Array中最小的部分跟當下比對，我們直接看代碼：

大家加油。

上一篇：[062] LeetCode 11 演算法【Container With Most Water】盛水最多的容器

下一篇：[064] LeetCode 334演算法【Increasing Triplet Subsequence】遞增三元子序列