As required by the problem, calculate the amount of trapped water.
First, find the maximum value within a segment that is greater than the smaller of the two boundary values. If such a value exists, split the problem into left + max index and max index + right.
If no such maximum exists, it means both boundaries are larger than all middle elements, so simply sum up the trapped water.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int sum;
void WaterStep(int A[],int left,int right) {
int min = A[left] > A[right] ? A[right] : A[left];
int max = min;
int index = -1;
for(int i = left+1; i < right; i++) {
if(A[i] > max) {
index = i;
max = A[i];
}
}
if(index == -1) {
for(int i = left+1; i < right; i++)
sum += min - A[i];
}
else {
WaterStep(A, left, index);
WaterStep(A, index, right);
}
}
int trap(int A[], int n) {
sum = 0;
WaterStep(A, 0, n-1);
return sum;
}
};
|