C++, two pointer solution, 8ms, easy to understand


  • 1
    H
    class Solution {
    public:
    int trap(vector<int>& height) {
          if(height.size()<=1) return 0;
          int i = 0;
          int* p = new int[height.size()];//access array is faster than vector, so i copy height to the array
          for(i = 0; i<height.size(); i++) p[i] = height[i];
          i = 0;
          while(!p[i]) i++;
          int pointer = i, min = p[i], res = 0;
          for(i++; i<height.size(); i++){
        	  if(p[i]<p[pointer]){
        		  if(p[i]>min){
        			  for(int j = i-1; p[j]<p[i]; j--){
        				  res += p[i]-p[j];
        				  p[j] = p[i];
        			  }
        		  }
        		  min = p[i];
        	  }
        	  else{
        		  for(int j = i-1; j>=pointer; j--){
        			  res += p[pointer]-p[j];
        		  }
        		  pointer = i;
        	  }
          }
      return res;
      }
      };

  • 1
    P

    c++, 8 ms solution

    class Solution {
    public:
    int trap(vector<int>& height) {

        unsigned int len = (unsigned int)height.size();
        if(len <= 2)
            return 0;
        
        len = len - 1;
    
        int min1 = 0;
        int max1 = 0;
        int min2 = len;
        int max2 = len;
        
        // left side
        while(((max1+1) <= len) && (height[max1+1] >= height[max1])) max1++;
        min1 = max1;
        max1++;
        
        // right side
        while( ((max2-1) >=0) && (height[max2-1] >= height[max2])) max2--;
        min2 = max2;
        max2--;
        
        int water = 0;
        
        while(max1 < max2) {
             if(height[min1] <= height[min2]) {
                while((max1 <= len) && (max1 < max2) && (height[max1] < height[min1])) {
                    int value = height[min1] - height[max1];
                    water += value;
                    max1++;
                }
                if(max1 == len) {
                    break;
                }
                if(max1 < max2) {
                min1 = max1;
                max1++;
                }
            }
            else {
                while((max2 >= 0) && (max1 < max2) && (height[max2] < height[min2])) {
                    int value = height[min2] - height[max2];
                    water += value;
                    max2--;
                }
                if(max2 == 0) {
                    break;
                }
                if(max2 > max1) {
                    min2 = max2;
                    max2--;
                }
            }
        }
            
        int wa =0;
        if(max1 == max2) {
           wa = max(0,min((height[min1]-height[max1]),(height[min2]-height[max2])));
        }
        water += wa;
        return water;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.