class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;
        int n = height.length;
        int left = 0, right = n - 1;
        int leftHigh = 0, rightHigh = n - 1;

        int sum = 0;
        while (left < right){
            if (height[leftHigh] < height[rightHigh]){
                left++;
                if (height[leftHigh] >= height[left]){
                    sum += height[leftHigh] - height[left];
                }
                else{
                    leftHigh = left;
                }
            }
            else{
                right--;
                if (height[rightHigh] >= height[right]){
                    sum += height[rightHigh] - height[right];
                }
                else{
                    rightHigh = right;
                }
            }
        }

        return sum;
    }
}