# 資訊

:::info
- Question: 42. Trapping Rain Water
- From: Leetcode Daily Challenge 2024.04.12
- Difficulty: Hard
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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:
:::success
* 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:
:::success
* Input: `height = [4,2,0,3,2,5]`
* Output: 9
:::

> Constraints:
:::success
* `n` == `height.length`
* 1 <= `n` <= $2 * 10^4$
* 0 <= `height[i]` <= $10^5$
:::

---

# 解法

## 概念

這題如果能找到每一個位置的左右最高點就可以了，因為最高點會把中間區域框起來，但如過要用 one pass 就不太容易，那個修正應該不好做，所以會用 DP 的方式先把痕跡寫下來，等等再來用

所以程式碼 12 到 23 行就是在做這件事情，而最後 26 到 28 行則是在計算每一個地方可以被積攢的雨水有多少

說 hard 好像也沒有到很 hard

## 程式碼

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        n = len(height)

        # Find left and right highest wall of each element
        leftWall = []
        rightWall = []
        maxCurrLeftWall = 0
        maxCurrRightWall = 0

        leftWall.append(0)  # No left wall for first element
        maxCurrLeftWall = max( maxCurrLeftWall, height[0] )
        for i in range( 1, n):
            leftWall.append( maxCurrLeftWall )
            maxCurrLeftWall = max( maxCurrLeftWall, height[i] )

        rightWall.append(0)
        maxCurrRightWall = max( maxCurrRightWall, height[n-1] )
        for i in range( n-2, -1, -1 ):
            rightWall.append( maxCurrRightWall )
            maxCurrRightWall = max( maxCurrRightWall, height[i] )
        rightWall.reverse()

        # Calculate the result
        for i in range( n ):
            val = min( leftWall[i], rightWall[i] ) - height[i]
            ans += val if val > 0 else 0
        return ans

---

# 複雜度

## 時間複雜度

創建 DP array 各花了 $O(n)$，真正計算答案也花了 $O(n)$，整體是 $O(n)$


## 空間複雜度

存放了兩個 DP array，所以是 $O(n)$