Givennnon-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], return6.
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!
题意：求出装水的多少。
思路：如果我们能做到每次到每个位置的时候就能得到答案的话，那么复杂度就低了，所以我们可以想如果每次存在一个高的紧接着是一个相对矮的话，就能计算了，，但是我们还要确保它的右边也能装下，所以我们先找到最高的那个，然后分成左右两边计算，再多一个curMax就能按照前面的思路计算了
class Solution {public:int trap(int A[], int n) {int ans = 0;int maxIndex = 0;for (int i = 1; i < n; i++)if (A[i] > A[maxIndex])maxIndex = i;int curMax = A[0];for (int i = 1; i < maxIndex; i++) {if (A[i] > curMax)curMax = A[i];else ans += curMax – A[i];}curMax = A[n-1];for (int i = n-2; i > maxIndex; i–) {if (A[i] > curMax)curMax = A[i];else ans += curMax – A[i];}return ans;}};
含泪播种的人一定能含笑收获。
