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、计算每一格的储水量valuelen-本身格子的高度然后所有容量相加。class Solution { public: int trap(vectorint height) { int nheight.size(); if(n2) return 0; vectorint left_hei(n,0),right_hei(n,0); int ans0; int left_maxheight[0],right_maxheight[n-1]; for(int i1;in-1;i){ left_maxleft_maxheight[i-1]?left_max:height[i-1]; left_hei[i]left_max; } for(int in-2;i0;i--){ right_maxright_maxheight[i1]?right_max:height[i1]; right_hei[i]right_max; } for(int i1;in-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; } };