Problem Description

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.

Examples

Example 1:

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

Constraints:

• n == height.length
• 1 <= n <= 2 * $10^4$
• 0 <= height[i] <= $10^5$

解析

給定一個非負整數陣列 height

每個height[i] 代表在 i 位置的高度

假設每個 height[i] 寬度是 1 單位長度

如果要在位置 i 累積雨水

需要有存在 0 ≤ k < i , i < j ≤ len(height) - 1 使得 min (height[j], height[k]) > height[i]

且累積的雨水面積 = min (height[j], height[k]) - height[i]