My easy-understanding Java solution with thinking process


  • 1

    While, this is my first time solving a hard problem. After drawing on the paper, I get the idea:

    • We need to find the V shapes to calculate the trapped water.
    • Find the start of a decreasing sequence (p1)
    • The end of the decreasing sequence (bottom)
    • And the end of an increasing sequence (p2).
    • V shape is bounded by p1, p2.
    • I got WA since there might be nested V shapes.
    • When calculating trapped water, fill the V shape.
    • Repeat until the result remains the same.
    • AC

    Attached is my Java code, though it is looooong.

    public class Solution {
      public int trap(int[] height) {
        int n = height.length;
        if(n<3) return 0;
        int p1=0,p2=1,bottom=0,i=0,j,count=0, count1=count;
        while(true){
          count1=count;
          i=0;
          while(i<n){
            //find start of V shape
            for(j=i;j<n;j++){
              if(j==n-1) break;
              if(height[j]>height[j+1]) break;
            }
            p1 = j;
            //If p1 is the end of input, there is no bottom and end of the V shape.
            if(p1==n-1) break;
            //find bottom of V shape
            for(j=p1+1;j<n-1;j++)
              if(height[j]<height[j+1]) break;
            bottom = j;
            //find end of V shape
            for(j=bottom+1;j<n-1;j++)
              if(height[j]>height[j+1]) break;
            p2 = j;
            //Check whether it is a valid V shape: 0<=i<=bottom<=j<=n-1
            if(p2>=n) break;
            //Add the trapped water
            int tmp=height[p1]<height[p2]?height[p1]:height[p2];
            for(j=p1+1;j<=p2-1;j++)
              if(tmp>height[j]){ 
                count+=(tmp-height[j]);
                height[j]=tmp;
              }
            i=p2;
            }
            //If we all V shapes are calculated
            if(count1==count) break;
          }
          return count;
        }
      }

Log in to reply
 

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