題目：

Given?n?non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,?
Given?[0,1,0,2,1,0,1,3,2,1,2,1], return?6.

思路：

題目的意思是說，給定一非負的整數(shù)數(shù)組，數(shù)組的每個數(shù)字表示柱子的高度，如果把這些柱子組成一個容器，最多能盛多少水？

思路是這樣的，每個柱子(高度為h)所在的位置能夠裝的水的容量取決于它前面所有柱子的最高高度preHeight以及它后面所有柱子的最高高度postHeight，

即裝水的容量等于max(0,min(preHeight-postHeight)-h)；

因此可以通過計算給定數(shù)組的前綴數(shù)組的最大值（如preMax[i]表示數(shù)組從0到i-1位置的最大值）；以及后綴數(shù)組的最大值（如postMax[i]表示數(shù)組從i到n-1位置的最大值），就可以利用上面的公式計算每個位置的水容量，最后加起來就是總共的容量。

代碼：

#include<iostream> #include<vector> #include<stdlib.h>using namespace std;int MaxTrappingWater(const vector<int> &water){int sz=water.size();vector<int> preMaxWater(sz);preMaxWater[0]=0;for(int i=1;i<sz;i++){if(water[i]>preMaxWater[i-1])preMaxWater[i]=water[i];elsepreMaxWater[i]=preMaxWater[i-1];}vector<int> sufMaxWater(sz);sufMaxWater[sz-1]=0;for(int i=sz-2;i>=0;i--){if(water[i]>sufMaxWater[i+1])sufMaxWater[i]=water[i];elsesufMaxWater[i]=sufMaxWater[i+1];}int sum=0;for(int i=0;i<sz;i++){sum+=max(0,min(preMaxWater[i],sufMaxWater[i])-water[i]);} return sum; }int main(){int n;while(cin>>n){vector<int> water(n,0);for(int i=0;i<n;i++)cin>>water[i];cout << MaxTrappingWater(water) <<endl;}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/AndyJee/p/4821590.html

總結(jié)

以上是生活随笔為你收集整理的（算法）Trapping Rain Water I的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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