[leetcode] 42. Trapping Rain Water解題レポート

タイトルリンク:https://leetcode.com/problems/trapping-rain-water/
Given n non-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] , return  6 .
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
考え方:two pointは左右の両端を指し、現在左右同時に達成できる最大の高さを維持し、面積の小さい一端を先に移動させ、新しい高さが現在の最高高さより小さい場合、その高さ差はいくつかの水を貯蔵することができる.1つの高いに当たる左右同時に到達可能な高さが増加すると更新される.
コードは次のとおりです.

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size()-1, ans =0, Min =0;
        while(left <= right)
        {
            int val = min(height[left], height[right]);
            if(val < Min) ans += (Min - val);
            else Min = val;
            height[left]<=height[right]?left++:right--;    
        }
        return ans;
    }
};