https://leetcode.com/articles/trapping-rain-water/
做完了一道hard难度的题目，个人还是很激动的，突然那觉得“双指针”简直就是神器，题目要求整个容器能盛下的水的数量，直观上来看，只有凹槽部分才能盛水，暴力搜索法复杂度太高，最佳方法是使用双指针，左右各放置一个，注意到盛水的多少是较短的那一边决定，如果左边高度小于右边，那么继续检查左边高度是否大于等于left_max，如果是更新left_max，否则累加存水量；右边情况类似，
代码如下
1 class Solution { 2 public: 3 int trap(vector<int>& height) { 4 //自己根据官方答案伪代码完成 5 int len = height.size(); 6 int left = 0, right = len - 1; 7 //int ans = 0, left_max = height[left], right_max = height[right]; 8 int ans = 0, left_max = 0, right_max = 0; //这里mgax都要初始化为0，否则会出错，比如height为空，上面的代码会访问下标为-1的元素 9 while (left < right) 10 { 11 if (height[left] < height[right]) 12 { 13 if (height[left] >= left_max) 14 left_max = height[left]; 15 else 16 ans += left_max - height[left]; 17 left++; 18 } 19 else 20 { 21 if (height[right] >= right_max) 22 right_max = height[right]; 23 else 24 ans += right_max - height[right]; 25 right--; 26 } 27 } 28 return ans; 29 } 30 };
时间复杂度：O(n)
空间复杂度：O(1)
二刷，2018-03-14，漏掉更新righ与left的部分了