42.接雨水--dp版本

左右两个dp，分别存储左侧的最高的元素和右侧的最高元素，每个点的元素就是左右两个最高元素的最小值减去自己的

class Solution {
public:
    int trap(const vector& height) {
	int n = static_cast(height.size());
	vectorleft(n),right(n);
	left[0] = height[0];
	right[n-1] = height[n-1];
	for(int i=1;i=0;--i)
		right[i] = max(right[i+1],height[i+1]);

	vectorret(n);
	for(int i=0;i