---
title: "#42 Trapping Rain Water"
tags: LeetCode, Top100
---
#42 Trapping Rain Water
==

題目描述
--
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.

Example 1:
--
>Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

解題思維
--
利用暴力法，找出當前單位高度所能聚集的水量。

Brute force
--

class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        for i in range(1, len(height)-1):
            leftWall = max(height[:i])
            rightWall = max(height[i+1:])
            if min(leftWall, rightWall) > height[i]:
                res += min(leftWall, rightWall)-height[i]

        return res

解題思維
--
暴力法雖然方便簡單去思考，但速度執行速度太慢了。
這裡借鏡DP演算法的思維，分別從左跟從右去建立當前的最佳解，再逐一去比較哪個才是真正的雨量累積。

Dynamic Programming
--

class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        length = len(height)
        if length == 0:
            return 0
        leftWall = [0 for i in range(length)]
        rightWall = [0 for i in range(length)]
        leftWall[0] = height[0]

        for i in range(1, length):
            leftWall[i] = max(height[i], leftWall[i-1])

        rightWall[length-1] = height[length-1]
        for i in range(length-2, -1, -1):
            rightWall[i] = max(height[i], rightWall[i+1])

        for i in range(0, length):
            res += min(leftWall[i], rightWall[i])-height[i]
        return res

解題思維
--
利用兩個指針去夾出雨量聚集的結果

Two pointers
--

class Solution:
    def trap(self, height: List[int]) -> int:
        res = 0
        left, right = 0, len(height)-1
        if len(height) == 0:
            return 0
        rightMax, leftMax = 0, 0
        while (right != left):
            if(height[right] > height[left]):
                if height[left] >= leftMax:
                    leftMax = height[left]
                else:
                    res += leftMax - height[left]
                left += 1
            elif (height[right] <= height[left]):
                if height[right] >= rightMax:
                    rightMax = height[right]
                else:
                    res += rightMax - height[right]
                right -= 1

        return res