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!

本题利用短板效应，从两端开始，依此寻找最短边所能存储到的最多的水，然后更新最短边。例如left height=1，right height=2，然后从左侧寻找，height=2，left height=2，water+=1。时间：8ms。代码如下：

class Solution {public:    int trap(vector
     
      & height) {        if (height.empty() || height.size() == 1)            return 0;        int left = 0, right = height.size() - 1;        int water = 0;        while (left < right){            if (height[left] < height[right]){                int i = left + 1;                while (i < right && height[i] < height[left])                    water += height[left] - height[i++];                left = i;            }            else{                int i = right - 1;                while (i > left && height[i] < height[right])                    water+=height[right] - height[i--];                right = i;            }        }        return water;    }};