42. Trapping Rain Water

题目描述

Givennnon-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.

解题方法

大致可分為兩種case, 先處理小的一邊

1. L<= R: 先處理Ｌ

mleft++;

   :當 left < mLeft:      left = mleft;   

   else:    vol += height\[left\] - height\[mLeft\]

1. L >R: 先處理R

    public int trap(int[] height){
        //corner case
        if(height == null || height.length < 3){
            return 0;
        }

        int left = 0;
        int mLeft = 0;
        int right = height.length - 1;
        int mRight = height.length - 1;
        int maxVol = 0;
        while(mLeft < mRight){
            if(height[left] < height[right]){
                mLeft++;
                if(height[left] < height[mLeft]){
                    left = mLeft;
                }else{
                    maxVol +=  (height[left] - height[mLeft]);
                }
            }else{
                mRight--;
                if(height[mRight] > height[right]){
                    right = mRight;
                }else{
                    maxVol += (height[right] - height[mRight]);
                }
            }
        }
        return maxVol;
    }