leetcode 42. Trapping Rain Water

采得百花成蜜后，为谁辛苦为谁甜。这篇文章主要讲述leetcode 42. Trapping Rain Water相关的知识，希望能为你提供帮助。
link
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.

文章图片

题意：看文字比较奇怪，看图片很清晰。给出每块的高度，求出往上面倒水那坨东西里可以存放多少水。

思路：
【leetcode 42. Trapping Rain Water】每个bar 能存多少水取决于它左边的最高的bar的高度和右边最高的bar的高度的较小的那个，与其自身高度的差。
因此方法很简单，从左到右扫一次可以算出每个bar左边的最高高度。从右到左扫一次可以算出每个bar右边的最高的高度。

code：

class Solution { public: int trap(vector< int> & height) { if(height.size() == 0) return 0; vector< int> leftMax(height.size()); leftMax[0] = height[0]; for(int i = 1 ; i < height.size(); i++){ leftMax[i] = max(leftMax[i-1], height[i]); } int rightMax = INT_MIN; int ans = 0; for(int i = height.size() - 1; i > = 0; i--){ rightMax = max(rightMax, height[i]); ans += (min(rightMax, leftMax[i]) - height[i]); } return ans; }};