42. Trapping Rain Water

class Solution {
public:
    int trap(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int leftMax = height[left], rightMax = height[right];
        int res = 0;

        while(left < right)
        {
            if(leftMax < rightMax)
            {
                leftMax = max(leftMax, height[++left]);
                res += leftMax - height[left];
            }
            else
            {
                rightMax = max(rightMax, height[--right]);
                res += rightMax - height[right];
            }
        }
        return res;
    }
};

• T: $O(N)$
• S: $O(1)$