42.?接雨水

---

題目：

給定?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 *
• 0 <= height[i] <=

---

思路：

首先，獲取數(shù)組長度。

其次，獲取每一個點的左側和右側的最大高度。

最后，找到每一個點左側和右側最大高度較小的那個（因為只有較小的那個高度才能限制雨水容量）。將這個減去該位置的高度，即可得到該位置的雨水單位數(shù)，將其累加到最終結果中。

---

代碼：

class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n == 0) {return 0;}vector<int> leftMax(n);leftMax[0] = height[0];for (int i = 1; i < n; ++i) {leftMax[i] = max(leftMax[i - 1], height[i]);//cout << leftMax[i] << '|';}//cout << endl;vector<int> rightMax(n);rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; --i) {rightMax[i] = max(rightMax[i + 1], height[i]);//cout << rightMax[i] << '|';}//cout << endl;int ans = 0;for (int i = 0; i < n; ++i) {ans += min(leftMax[i], rightMax[i]) - height[i];//cout << min(leftMax[i], rightMax[i]) - height[i] << '|';}return ans;}
};

?