Share C++ and Python, O(n) time, O(1) space


  • 0
    W

    C++ 8 ms

    class Solution {
        public:
            int trap(vector<int>& height) {
                int n=height.size();
                if(n<=2) return 0;
                int s=0; int e=n-1; int area1=0; int area2=0; int minh=0;
                while(e>s){
                    if(height[e]<=minh){area2+=height[e];e--;}
                    else if (height[s]<=minh){area2+=height[s];s++;}
                    else if (height[e]>=height[s]){
                        area2+=height[s];area1+=(height[s]-minh)*(e-s+1);minh=height[s];s++;}
                    else {area2+=height[e];area1+=(height[e]-minh)*(e-s+1);minh=height[e];e--;}
                } area2+=height[e];
                area1+=(height[e]>minh?height[e]-minh:0);
                return area1-area2; }
        };
        class Solution(object):
                def trap(self, height):
                    """
                    :type height: List[int]
                    :rtype: int
                    """
                    n=len(height)
                    if n<=2:
                        return 0
                    s=0
                    e=n-1
                    area=0
                    minh=0
                    while e>s:
                        if height[e]<=minh:
                            e-=1
                        elif height[s]<=minh:
                            s+=1
                        elif height[e]>=height[s]:
                            area+=(height[s]-minh)*(e-s+1)
                            minh=height[s]
                            s+=1
                        elif height[s]>height[e]:
                            area+=(height[e]-minh)*(e-s+1)
                            minh=height[e]
                            e-=1
                    area+=max((height[e]-minh),0)
                    return area-sum(height)

Log in to reply
 

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