1.问题描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [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.输入说明
输入若干个非负整数，以空格分隔。
3.输出说明
输出一个整数，表示结果。
4.范例
输入：
0 1 0 2 1 0 1 3 2 1 2 1
输出：
6
5.思路
备忘录优化--经典面试题：接雨水问题详解 - 知乎 (zhihu.com)
在位置 i 能接多少水，取决于该位置左边最高柱子的高度和右边最高柱子的高度，取两边中最高柱子高度的最小高度来计算接多少水，位置i最大的水柱高度为：min(l_max, r_max)，接的水量为： min(l_max, r_max) - height[i] 。
开两个数组 r_max 和 l_max 充当备忘录，l_max[i] 表示位置 i 左边最高的柱子高度，r_max[i] 表示位置 i 右边最高的柱子高度。预先把这两个数组计算好，避免重复计算：
// 从左向右计算 l_max for (int i = 1; i < n; i++) l_max[i] = max(height[i], l_max[i - 1]); // 从右向左计算 r_max for (int i = n - 2; i >= 0; i--) r_max[i] = max(height[i], r_max[i + 1]);
6.代码
#include<iostream> #include<vector> #include<stdio.h> using namespace std; class Solution { public: int trap(vector<int>& height)//数组首地址 { if(height.empty()) return 0; int len=height.size(); int sum=0; int l_max[len],r_max[len]; l_max[0]=height[0]; r_max[len-1]=height[len-1]; for(int i=1;i<len;i++) { l_max[i]=max(height[i],l_max[i-1]); } for(int i=len-2;i>=0;i--) { r_max[i]=max(height[i],r_max[i+1]); } for(int i=1;i<len-1;i++) { sum +=min(l_max[i],r_max[i])-height[i]; } return sum; } }; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int h; vector<int> v; while(cin>>h) { v.push_back(h); } int res=Solution().trap(v); cout<<res<<endl; return 0; }