Two pointers, c++ 8ms, easy to understand


  • 2
    R
    class Solution {
    public:
        int trap(vector<int>& height) {
            // Two pointers
            
            // for each bar (height[i]) in map, 
            // how much water it can contain depends on height[i] and the largest value before (left) and after height[i] (right)
            // area i = min(left, right) - height[i] (second largest value - height[i])
            // So, we use two pointers to scan the map, one scan from left to right, one scan from right to left.
            // At each step:
            //     Update the second larget value(second) up to now;  
            //     Calculate arear i = second - height[i];
            //     Update the smaller one.
            
            int left = 0, right = height.size()-1;
            if(right < 2) return 0;
            int leftMax = height[left] , rightMax = height[right], second;
            int area = 0;
            while(left < right){
                leftMax = max(leftMax, height[left]);
                rightMax = max(rightMax, height[right]);
                second = min(leftMax, rightMax);
                if(height[left] < height[right]){
                    area += second - height[left];
                    left++;
                }else{
                    area += second - height[right];
                    right--;
                }
            }
            return area;
        }
    };

Log in to reply
 

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