42. Trapping Rain Water

解題思路

這題看題目時沒想法，但看完 neetcode 的解法後恍然大悟。我覺得分析問題時，如果當下沒辦法想出演算法，可以先用人類笨方法思索人類會怎麼解問題。確定這解法 ok 後，再轉換成比較電腦的形式，一步步轉換過去。

程式碼

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), ans = 0, minHeight;
        vector<int> leftMax(n, 0);
        vector<int> rightMax(n, 0);

        for(int i=1; i<n; i++)
        {
            leftMax[i] = max(leftMax[i-1], height[i-1]);
            rightMax[n-1-i] = max(rightMax[n-i], height[n-i]);
        }
        for(int i=0; i<n; i++)
        {
            minHeight = min(leftMax[i], rightMax[i]);
            ans += max(minHeight - height[i], 0);
        }
        
        return ans;
    }
};