Clear C++ Solution 11ms


  • 15
    S

    Count the rocks cell first, then the total cell.
    The key thing here is that if a cell has some rock on both left and right that higher than itself, it will either be water or rock.

    class Solution {
    public:
        int trap(int A[], int n) {
            int summap = 0;
            int sumtot = 0;
            
            for(int i = 0; i < n; i++) summap += A[i];
            
            int left = 0, right = n - 1;
            int leftbar = 0, rightbar = 0;
            while(left <= right) {
                leftbar = max(A[left], leftbar);
                rightbar = max(A[right], rightbar);
                
                if(leftbar <= rightbar) {
                    sumtot += leftbar;
                    left++;
                } else {
                    sumtot += rightbar;
                    right--;
                }
            }
            
            return sumtot - summap;
        }
    };

  • 0
    X

    Good solution! I am just wonder how you test the running time of your solution? under which enviroment? Thanks!


  • 0
    S

    Upon submission it gives the time


  • 0
    X

    Thanks! It's convinient!


  • 0

    similar to the top voted solution ! nice implementation!


Log in to reply
 

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