Java solution with comments, O(n) time


  • 0
    T
    public class Solutions {
        public int trap(int[] height) {
            // corner case
            if (height == null || height.length < 3) return 0;
            // hi is the index of the highest pole
            int total = 0, hi = 0;
            // first thing is to find the highest's index
            for (int i = 1; i < height.length; i++) {
                if (height[i] > height[hi]) {
                    hi = i;
                }
            }
            // each round we start from a pole and find the next one that is equal or higher than it
            // it's guaranteed that there must be at least one pole >= current pole before (include) the highest pole
            // records the obstacles between those two poles so we will subtract that part
            int cur = 0, next = 0, obstacle = 0;
            while (cur != hi) {// loop util cur reached hi (left -> right)
                next = cur + 1;
                while (height[cur] > height[next]) { // loop until we find the next pole >= cur pole
                    obstacle += height[next]; // records the obstacles
                    next++;
                }
                // now, next pole is equal or larger than cur, we can add some to total
                total += (next - cur - 1) * height[cur] - obstacle; // do not forget to - 1
                obstacle = 0;
                cur = next; // start next round, current pole should be the one we found last round
            }
    
            // do it from right -> left
            cur = height.length - 1;
            while (cur != hi) {
                next = cur - 1;
                while (height[cur] > height[next]) {
                    obstacle += height[next];
                    next--;
                }
                total += (cur - next - 1) * height[cur] - obstacle;
                obstacle = 0;
                cur = next;
            }
            // finished
            return total;
        }
    }
    

    Time complexity should be in 2n


Log in to reply
 

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