題目介紹

給定 n 個非負整數(shù)表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。 

示例 2：

輸入：height = [4,2,0,3,2,5]
輸出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

解答

C++解法

class Solution {
public:int trap(vector<int>& height) {// 雙指針 前后最大值// 每個位置左邊和右邊最高高度分別記錄在數(shù)組上// 每個位置可以儲水的容量取決于其左右兩邊最大值之小者if(height.size() <= 2) return 0;vector<int> maxLeft(height.size(), 0);vector<int> maxRight(height.size(), 0);int size = maxRight.size();// 記錄每個柱子左邊的最大高度maxLeft[0] = height[0];for(int i = 1; i < size; ++i){maxLeft[i] = max(maxLeft[i - 1], height[i]);}maxRight[size - 1] = height[size - 1];for(int i = size - 2; i >= 0; --i){maxRight[i] = max(maxRight[i + 1], height[i]);}int res = 0;for(int i = 1; i < size; ++i){res += min(maxRight[i], maxLeft[i]) - height[i];}return res;}
};

python3

class Solution:# 每一個位置能盛放多少水取決于其左邊和右邊柱子的最大高度的小者def trap(self, height: List[int]) -> int:n = len(height)# pre_max[i] 表示下標為i的柱子前面(包括下標為i的柱子)的最大高度pre_max = [0] * npre_max[0] = height[0] for i in range(1, n):pre_max[i] = max(pre_max[i - 1], height[i])# suf_max[i] 表示下標為i的柱子(包括下標為i的柱子)后面的最大高度suf_max = [0] * nsuf_max[-1] = height[-1]#n-2 ~ 0 for i in range(n - 2, -1, -1):suf_max[i] = max(suf_max[i + 1], height[i])ans = 0# zip 將其中的列表打包成元組的列表用來迭代for h, pre, suf in zip(height, pre_max, suf_max):ans += min(pre, suf) - hreturn ans