题目描述：

https://leetcode.com/problems/trapping-rain-water/

解决方法：

https://leetcode.com/problems/trapping-rain-water/solution/

optim_code(c++):

int trap(vector<int>& height)
{
    int left = 0, right = height.size() - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
            ++left;
        }
        else {
            height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
            --right;
        }
    }
    return ans;
}

心得：

Approach 1: Brute force
将问题分割的思想，并不是一次一个部分trap的大小，而是进行分解，一次就求解一个上面trap的大小。在算左侧最大时，会把本身的值算进去。因为trap必须比本身大。右侧同理。
Approach 2: Dynamic Programming
方法中依次找出左侧或者右侧最大的值的思想很好，每次都是max(height[i], left_max[i - 1])，其实就是找到了左侧的最大值。右侧同理。

Approach 3: Using stacks
思路奇特，较难理解
Approach 4: Using 2 pointers
需观察算法特点，在approach2的基础基础上优化