題目介紹

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

示例 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 個(gè)單位的雨水（藍(lán)色部分表示雨水）。 

示例 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) {// 雙指針 前后最大值// 每個(gè)位置左邊和右邊最高高度分別記錄在數(shù)組上// 每個(gè)位置可以儲(chǔ)水的容量取決于其左右兩邊最大值之小者if(height.size() <= 2) return 0;vector<int> maxLeft(height.size(), 0);vector<int> maxRight(height.size(), 0);int size = maxRight.size();// 記錄每個(gè)柱子左邊的最大高度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:# 每一個(gè)位置能盛放多少水取決于其左邊和右邊柱子的最大高度的小者def trap(self, height: List[int]) -> int:n = len(height)# pre_max[i] 表示下標(biāo)為i的柱子前面(包括下標(biāo)為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] 表示下標(biāo)為i的柱子(包括下標(biāo)為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