LeetCode 42. Trapping Rain Water

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.

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!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
解析：
给出了一个高度图，高度由数组中的数值来表示，两边高中间低的情况会形成一个坑，这样的坑可以存水，计算存放水的单位数量。
解法1:
指针法，采用两个指针left和right，分别指向首尾，从两边向中间扫描，在当前两指针确定的范围内，先比较两头找出较小值，如果较小值是left指向的值，则从左向右扫描，如果较小值是right指向的值，则从右向左扫描，若遇到的值比当较小值小，则将差值存入结果，如遇到的值大，则重新确定新的窗口范围，以此类推直至left和right指针重合.
代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() -1;
        int result = 0;
        while(left < right)
        {
            int min_num = min(height[left], height[right]);//选择左右指针中较小的数值
            if(min_num == height[left])//如果左边较小 
            {
                left ++;
                while(left < right && height[left] < min_num)//从左向右遍历，找到比left小的数值，计算差值
                {
                    result += min_num - height[left++];
                }
            }else
            {
                right --;
                while(left < right && height[right] < min_num)
                    result += min_num - height[right--];
            }
        }
        return result;
    }
};

运行结果：
解法2:
思路与解法1相同，只是代码看上去更简洁。

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size()-1;
        int level = 0, result = 0;
        while(left < right)
        {
            int min_index = height[left] < height[right] ?left ++: right --;
            int lower = height[min_index];
            level = max(level, lower);
            result += level - lower;
        }
        return result;
    }
};

运行情况：
解法3:
采用栈来实现。具体做法是，遍历高度，如果此时栈为空，或者当前高度小于等于栈顶高度，则把当前高度的坐标压入栈，注意我们不直接把高度压入栈，而是把坐标压入栈，这样方便我们在后来算水平距离。当我们遇到比栈顶高度大的时候，就说明有可能会有坑存在，可以装雨水。此时我们栈里至少有一个高度，如果只有一个的话，那么不能形成坑，我们直接跳过，如果多于一个的话，那么此时把栈顶元素取出来当作坑，新的栈顶元素就是左边界，当前高度是右边界，只要取二者较小的，减去坑的高度，长度就是右边界坐标减去左边界坐标再减1，二者相乘就是盛水量。
代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int i = 0, res = 0, n = height.size();
        while (i < n) {
            if (st.empty() || height[i] <= height[st.top()]) {
                st.push(i++);
            } else {
                int t = st.top(); st.pop();
                if (st.empty()) continue;／／注意此时i并没有递增，下次遍历重新入栈
                res += (min(height[i], height[st.top()]) - height[t]) * (i - st.top() - 1);
            }
        }
        return res;
    }
};

运行情况：

参考：
https://www.cnblogs.com/grandyang/p/4402392.html