7 接雨水

给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 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 1 <= n <= 2 * 104 0 <= height[i] <= 105

思路

1、判断参数的合法性。

2、每一格中能装多少水取决于他左边最高的格子和右边最高的格子，假设为left和right。因为木桶效应，装水量主要取决于left和right中最矮的那一根，将其定义为len。

3、循环找到数组中每一格的len，先创建一个存放左边最高格子的数组，再创建一个右边最高格子的数组。

4、计算每一格的储水量，value=len-本身格子的高度，然后所有容量相加。

class Solution { public: int trap(vector<int>& height) { int n=height.size(); if(n<2) return 0; vector<int> left_hei(n,0),right_hei(n,0); int ans=0; int left_max=height[0],right_max=height[n-1]; for(int i=1;i<n-1;i++){ left_max=left_max>height[i-1]?left_max:height[i-1]; left_hei[i]=left_max; } for(int i=n-2;i>0;i--){ right_max=right_max>height[i+1]?right_max:height[i+1]; right_hei[i]=right_max; } for(int i=1;i<n-1;i++){ if(height[i]>=min(left_hei[i],right_hei[i])) continue; ans+=(min(left_hei[i],right_hei[i])-height[i]); } return ans; } };