Sofie 舒霏的部落格

今天要來解的題目是 Leetcode－42. Trapping Rain Water ，難度為 Hard，

而我所使用的語言是 python3

壹、理解題目

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

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

其實這題是 11 Container With Most Water 的延伸題，

在做這題之前，可以先點進這裡看看解法喔！

貳、開始解題

我的第一個想法是切很多條水平線。

怎樣能夠裝水？一定是左右邊各有一條，才盛的了嘛！

因此我另開了一個變數（sort_height），是由大到小排列的 height，

以 Example 1 做舉例，sort_height = [3,2,1] （0 就不用管了

height = 3 時，顯然沒有辦法裝水，下一位～～～

height = 2 時，有 4 位柱子碰到紅線，分別是 x = 3, 7, 8, 10 這四個位子。

由於下一條紅線在 y=1，

所以可以儲存的水自然就落在 y=1 & y=2 之間，

分別是 x = 3~7 之間的，以及 x = 8~10 之間的紅色區域，

這兩塊紅色面積 = (7-3-1) + (10-8-1) = 4

再來，height = 1 時， x = 1, 3, 4, 6, 7, 8, 9, 10, 11 這些位子都碰到紅線。

雖然說箭頭很多，但其實真的有面積貢獻的只有 x=1~3 & x=4~6 這兩格，

其餘的箭頭只差一，是無法裝水的。

寫成 code 如下，

結果在最後一筆超大測資爆掉了 XD

仔細看一下，不僅 x 軸很多，y 軸 (height) 也超高，

這樣一條一條往下算儲存面積，要算超久啊！

參、解法二

讓我們重新思考這個問題，為何箭頭所指的地方可以裝水呢？

因為從箭頭出發，往左右兩邊各找到的 left_max & right_max 都比箭頭所指的那格來的高，所以可以裝水。

裝的水量呢？選 left_max & right_max 中比較小的那一個，然後再扣掉箭頭所指處的黑色高度，

在下圖中，left_max = 1、right_max = 3，所以可以盛的水 = 1 - 0 = 1

再看幾個例子，

min(left_max=2, right_max=3) - 1 = 1

min(left_max=3, right_max=3) - 3 = 0

min(left_max=3, right_max=1) - 1 = 0

問題來了？怎麼找到 left_max & right_max？

可以先用一個 list，把「不同箭頭所指的地方」的 left_max 存起來，

像是在這張圖中，從左掃到右，可以得到 left_max 們 = [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]。

接著，從右邊掃到左邊，right_max 們 = [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]

能不能更有效率一點？ 可以！

從左掃到右時，先令「可存到的 water」= left_max；

在從右掃到左時，不用特意建一個 right_max list，直接去更改「可存到的 water」，

結果－

肆、解法三

和上述解法概念相同，但上面的解法要用到一個 list，增加了空間複雜度 O(n)，

能不能只用 O(1) 就做到呢？

可以！用 2 pointers 來記錄 max_left & max_right！