leetcode042: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 Marcos for contributing this image!
问题分析
代码
//运行时间:13ms class Solution { public: int trap(vector<int>& height) { int i = 0, j = height.size()-1; int ans = 0; int h = 0; while (j-i >= 0){ if (height[i] > height[j]){ if (height[j] <= h){ ans += (h - height[j]); } else{ h = height[j]; } j--; } else if (height[i] < height[j]){ if (height[i] <= h){ ans += (h - height[i]); i++; } else{ h = height[i]; } } else{ if (height[i] <= h){ if (i != j) ans += 2 * (h - height[i]); else ans += (h - height[i]); } else{ h = height[i]; } i++; j--; } } return ans; } };
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。