給定 n 個非負(fù)整數(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 個單位的雨水（藍(lán)色部分表示雨水）。

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

提示：
n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

這道題可以用雙指針和單調(diào)棧求解，但是這里就只說動態(tài)規(guī)劃的解法；
既然要求解總雨水，我們可以把每一列的雨水量求出來，加起來即可；
每一列該怎么求呢？
以第 i 為例，只要能求出第 i 列左邊最高的一列 l 和右邊最高的一列 r ，那么min(l , r) - 第 i 列高度就是第 i 列的存水量了
總體思路就是 ：
1，另l[i] 為第 i 列左邊最高的一列，r[i]為第 i 列右邊最高的一列
2，分別求出每一列左邊最高的一列和右邊最高的一列
3，求雨水總和

代碼如下：

class Solution { public:int trap(vector<int>& height) {int n = height.size();if (n <= 2) return 0;vector<int> l(n, 0);//l是第i個柱子左邊最高的柱子vector<int> r(n, 0);//r是第i個柱子右邊最高的柱子// 記錄每個柱子左邊柱子最大高度l[0] = height[0];for (int i = 1; i < n; ++i) l[i] = max(height[i], l[i - 1]);// 記錄每個柱子右邊柱子最大高度r[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; --i)r[i] = max(height[i], r[i + 1]);//求總雨水量int sum = 0;for (int i = 0; i < n; ++i) {//第i個柱子與水量count為左邊最高柱子和右邊最高柱子的最小值減去該柱子的高度int count = min(r[i], l[i]) - height[i];if (count > 0) sum += count;//每一個柱子存水量相加就是總村存水量}return sum;} };

總結(jié)

以上是生活随笔為你收集整理的接雨水（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。