Problem
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
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!
Code
int trap(int A[], int n) { // Note: The Solution object is instantiated only once and is reused by each test case. int l = 0,area = 0;; while(l < n - 2){ int m = l; while(m < n - 1 && A[m] > A[m + 1]) ++m; if(m == n - 1) break; if(l == m){ ++l; continue; } int r = m,rmax = r; while(r < n && A[r] < A[l]){ if(A[rmax] < A[r]) rmax = r; ++r; } if(r == n){ r = rmax; } int h = min(A[l],A[r]); for(int i = l;i <= r;++i) area += h - min(A[i],h); l = r; } return area; }
No comments:
Post a Comment