42. Trapping Rain Water

 

42. Trapping Rain Water

Hard

477683FavoriteShare

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6

Accepted

372,679

Submissions

820,434

class Solution { public: int trap(vector<int>& height){ int left=0; int right=height.size()-1; int leftmax=0;//记录目前为止左指针左边最高的高度 int rightmax=0;//记录目前为止右指针右边最高的高度 int sum=0; while(left<right){ if(height[left]<height[right]){//如果此时左边的高度小于右边的高度，则一定可以盛水 if(leftmax<height[left]){//更新高度 leftmax=height[left]; }else{ sum+=(leftmax-height[left]);//计算盛水量 } left++; }else{ if(rightmax<height[right]){ rightmax=height[right]; }else{ sum+=(rightmax-height[right]); } right--; } } return sum; } };