根据题目要求,求出灌入水的多少。
先找出某段中的比两边界较小值 要大的最大值。如果存在该值,将问题拆分为 左+最大值的index和最大值的index+右。
如果不存在该最大值,表示两个边界都比中间的大,灌水求和即可。
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; } };