My straightforward Java O(n) solution


  • 2
    G

    public class Solution {

    // 1. find the max value index in height array

    // 2. sum up the water of each bin contains in the left side of max height from index 0.

    // 3. sum up the water of each bin contains in the right side of max height from index height.length - 1.

    public int trap(int[] height) {
        if(height == null || height.length <= 1){
            return 0;
        }
        int sum = 0;
        int index = 0;
        for(int i = 0; i < height.length; i++){
            if(height[i] > height[index]){
                index = i;
            }
        }
        
        int pre = -1;
        int i = 0;
        while(i < index){
            if(height[i] < pre){
                sum += (pre - height[i]);
            }
            else{
                pre = height[i];
            }
            i++;
        }
        
        i = height.length - 1;
        pre = -1;
        while(i > index){
            if(height[i] < pre){
                sum += (pre - height[i]);
            }
            else{
                pre = height[i];
            }
            i--;
        }
        return sum;
    }
    

    // This solution is easy to understand, but a better solution is to scan the array only once starting from both side.
    }


  • 0

    So smart. It's nearly a one-pass solution!


  • 0
    G

    thanks........ .


Log in to reply
 

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