LeetCode - Trapping Rain Water

登山则情满于山,观海则意溢于海。这篇文章主要讲述LeetCode - 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.

LeetCode - Trapping Rain Water

文章图片

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!
 
AC代码:
int right(int* a,int n){
      int ans = 0;
      int has = 0;
      int h = 0;
      for(int i = 0 ; i < n ; i ++){
              if(a[i]> =h){
                      ans+=has;
                      h=a[i];
                      has = 0;
              }else{
                      has+=h-a[i];
              }
      }
      return ans;
}
【LeetCode - Trapping Rain Water】int left(int*a,int n){
      int ans = 0;
      int has = 0;
      int h = 0;
      for(int i = n-1 ; i > = 0; i --){
              if(a[i]> h){
                      ans+=has;
                      h = a[i];
                      has = 0;
              }else{
                      has += h-a[i];
              }
      }
      return ans;
}
 
int trap(int* height, int heightSize) {
    return right(height,heightSize)+left(height,heightSize);
}  Trapping Rain Water
































    推荐阅读