leetcode42. Trapping Rain Water _leetcode

不操千曲而后晓声，观千剑而后识器。这篇文章主要讲述leetcode42. Trapping Rain Water相关的知识，希望能为你提供帮助。
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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

文章图片

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 Marcosfor contributing this image!
题目如上。假期最后一道hard难度的题，先放上之前实现的代码，还可以简化

1 class Solution { 2 public: 3int trap(vector< int> & height) { 4int sum=0; 5for(int i=0; i< height.size(); ++i){ 6for (int j=i+1; j< height.size(); ++j) { 7if(height[j]> =height[i]){ 8sum+=height[i]*(j-i-1); 9//可优化，m-> i 10for(int m=i+1; m< j; ++m){ 11sum-=height[m]; 12} 13i=j-1; 14break; 15} 16if(j==height.size()-1){ 17int max=height[i+1]; 18int max_i=i+1; 19for(int n=max_i+1; n< height.size(); ++n){ 20if(height[n]> max){ 21max=height[n]; 22max_i=n; 23} 24} 25sum+=height[max_i]*(max_i-i-1); 26for(int m=i+1; m< max_i; ++m){ 27sum-=height[m]; 28} 29i=max_i-1; 30} 31} 32 33} 34return sum; 35} 36 };

【leetcode42. Trapping Rain Water】