给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [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
0 <= n <= 3 * 104
0 <= height[i] <= 105
#include<iostream>
#include<stack>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
/*
第一遍在 vec[i] 中存入i位置左边的最大值，
然后开始第二遍遍历数组，
第二次遍历时找右边最大值，然后和左边最大值比较取其中的较小值，
然后跟当前值 height[i] 相比，如果大于当前值，则将差值存入结果
*/
class Solution {
public:
int trap(vector<int>& height)
{
int res = 0, maxvalue = 0, n = height.size();
vector<int> vec(n, 0);
for (int i = 0; i < n; ++i)
{
vec[i] = maxvalue;
maxvalue = max(maxvalue, height[i]);
}
maxvalue = 0;
for (int i = n - 1; i >= 0; --i)
{
vec[i] = min(vec[i], maxvalue);
maxvalue = max(maxvalue, height[i]);
if (vec[i] > height[i])
{
res += vec[i] - height[i];
}
}
return res;
}
};
int main()
{
int a[1000];
int x;
int i = 0;
vector<int> vec;
int target;
while (cin >> a[i])
{
vec.push_back(a[i]);
i++;//注意这里i++对输出结果的影响
x = cin.get();
if (x == '
')
break;
}
int ans = Solution().trap(vec);
cout << ans << endl;
system("pause");
return 0;
}