一：Trapping Rain Water
题目：
Givennnon-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], return6.
地址：https://leetcode.com/problems/trapping-rain-water/
这道题关键点是是两边往中间遍历，记录当前第二高点secHeight，然后利用这个第二高点减去当前历经的柱子，剩下就装水容量了。为什么是第二高点？因为两边比较，，最高的点不用动，只移动第二高点。
这也是阿里2015实习生招聘附加题第三题
class Solution {public:int trap(int A[], int n) {int secHeight = 0;int left = 0;int right = n-1;int area = 0;while(left < right){if(A[left] < A[right]){secHeight = max(A[left], secHeight); // 找到次最高点area += secHeight – A[left];left ++;}else{secHeight = max(A[right], secHeight);area += secHeight – A[right];right –;}}return area;}};
二：Container With Most Water
题目：
Givennnon-negative integersa1,a2, …,an, where each represents a point at coordinate (i,ai).nvertical lines are drawn such that the two endpoints of lineiis at (i,ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
链接：
https://leetcode.com/problems/container-with-most-water/
分析：此题和上一题很类似，上一题是柱子，这一题是线，求哪两根线之间的蓄水量最多，此题仍然是采用两边指针往中间遍历的思想，当height[left] < heght[right]，，只能left++(right–绝对会导致面积减小)，反之只能right–。
class Solution {public:int maxArea(vector<int> &height) {int left = 0, right = height.size()-1;int secHeight = 0;int area = 0;while(left < right){if(height[left] < height[right]){ // 如果左边小于右边 只能对left++(因为right– 只会更小) 并且求出此时面积与之前的对比area = max(area,height[left]*(right – left));left ++;}else{area = max(area,height[right]*(right – left)); // 如果右边小于左边，只能对right–，并且求出此时面积与之前对比right –;}}return area;}};
然后继续努力，把让自己跌倒的石头搬掉或绕过去，不就解决问题了吗
