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!
Solution:
基本思路是独立考虑每一个单位能容下的谁。比如上例中，坐标x~[2, 3]能装1个单位的水，[5, 6]能装2个单位的水，而能装的水的体积与该位置向左最高值LeftHighest，和向右最高值RightHighest相关。volume = max(0, min(LeftHighest, RightHighest))，有了这个认识，体积就很容易算出了。
class Solution { public: int *leftHigh, *rightHigh; int trap(int A[], int n) { if(n < 3) return 0; int volume = 0; leftHigh = new int[n], rightHigh = new int[n]; int left = 0, right = 0; for(int i = 0;i < n;i++) { leftHigh[i] = left; if(A[i] > left) left = A[i]; rightHigh[n - 1 - i] = right; if(A[n - 1 - i] > right) right = A[n - 1 - i]; } for(int i = 0;i < n;i++) volume += max(0, min(leftHigh[i], rightHigh[i]) - A[i]); return volume; } };