42.收集雨水（Trapping Rain Water）
方法一：利用双指针交叉循环求解，时间复杂度O(n)
//接雨水 int trap(vector<int>& height) { int i=0,j=height.size()-1; int left_max=0,right_max=0; int van=0; while(i<j) { if(height[i]<height[j]) { if(height[i]>left_max) { left_max=height[i]; i++; } else { van+=left_max-height[i]; //第一次漏掉了i++ i++; } } else { if(height[j]>right_max) { right_max=height[j]; j--; } else { van+=right_max-height[j]; j--; } } } return van; }
方法二：动态规划O(n)
int trap(vector<int>& height) { //动态规划,事先保存 int n=height.size(); vector<int> left_max(n); vector<int> right_max(n); int max=0; for(int i=0;i<n;i++) { if(height[i]>=max) { max=height[i]; } left_max[i]=max; //i++; 已经加过了 } max=0; for(int j=n-1;j>=0;j--) { if(height[j]>=max) { max=height[j]; } right_max[j]=max; //j-- ; } int ans=0; for(int i=0;i<n;i++) { if(height[i]<left_max[i]&&height[i]<right_max[i]) { //理解出错 ans+=min(left_max[i],right_max[i])-height[i]; } } return ans; }