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

动态规划：

将每一个位置点左侧的最大高度存起来，然后将每个位置点右侧的最大高度存起来，这样，该位置的最大存水量为min(maxleft[i], maxright[i])-height[i] 得到，最后将所有位置相加即可，为了提高空间复杂度方面的性能，我们只需要将所有位置对应的左侧最大高度存在一个数组中，然后每算出一个右侧最大高度，就将该位置对应的存水量算出来，接着进行下一位的计算。

class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> dp(height.size(), 0);
        int maxleft = 0;
        for (int i=0; i<height.size(); ++i) {
            dp[i] = maxleft;
            maxleft = max(height[i], maxleft);
        }
        int maxright = 0, res = 0;
        for (int i=height.size()-1; i>=0; --i) {
            dp[i] = min(dp[i], maxright);
            maxright = max(maxright, height[i]);
            if (dp[i]-height[i] > 0) {
                res += (dp[i]-height[i]);
            }
        }
        return res;
    }
};

class Solution {
    public int trap(int[] height) {
        if(height.length == 0)
        {
            return 0;
        }
        int[] maxleft = new int[height.length];
        int[] maxright = new int[height.length];
        
        int maxcur = height[0];
        maxleft[0] = height[0];
        for(int i=1; i<height.length; i++)
        {
            if(height[i] > maxcur)
                maxcur = height[i];
            maxleft[i] = maxcur;
        }
        maxcur = height[height.length-1];
        maxright[height.length-1] = height[height.length-1];
        for(int i=height.length-2; i>=0; i--)
        {
            if(height[i] > maxcur)
                maxcur = height[i];
            maxright[i] = maxcur;
        }
        int sum = 0;
        for(int i=0; i<height.length; i++)
        {
            sum += Math.min(maxleft[i], maxright[i]) - height[i];
        }
        return sum;
    }
}

two pointer:

1. 加入水后，图片的高度整体是从左右两边往中间的一个最高点单向增大的，所以这就给了我们一个很好的解题思路。先找到整张图的最高点，并记录它所在的位置，然后依次从左右两端往最该点遍历，遍历时记录左边遍历过的位置的最高点的值，当到达位置的实际高度小于我们记录的最高值，则表明此处有积水，由于宽度都是1，所以我们总积水的体积可以直接加上在此处实际高度与记录的最高高度的差值。当左右遍历完成后，所得结果及时总的积水体积。

class Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size();   //得到容器的大小 
        if(size <= 2) return 0;
        int max = -1, maxi = 0;

        for(int i=0; i < size; ++i){
            if(height[i] > max){
                max = height[i];    //找到最高点，并记录最高点所在的位置 
                maxi = i;
            }
        }
        int result = 0, nowheight=height[0];          //从左开始遍历 
        for(int j = 1; j < maxi;j++){
            if(nowheight <height[j]) nowheight = height[j];  //记录遍历过的点的最大值 
            else result += (nowheight - height[j]);          //最大值与现在值得差值即为此处积水 
        }
        nowheight = height[size-1];                          //从右开始遍历，方法与从左开始遍历一样 
        for(int k = size-1;k > maxi;k--){
            if(nowheight < height[k]) nowheight = height[k];
            else result += (nowheight - height[k]);
        }
        return result;
    }
};

2. 原理同上，但不用分开两次遍历，两边头同时开始，左小于右左一直进行，知道左大于等于右，右进行，然后右大于等于左，左进行，循环，最终到达左到右过程的最高点。

So, we can say that if there is a larger bar at one end (say right), we are assured that the water trapped would be dependant on height of bar in current direction (from left to right). As soon as we find the bar at other end (right) is smaller, we start iterating in opposite direction (from right to left). We must maintain left_max and right_max during the iteration, but now we can do it in one iteration using 2 pointers, switching between the two.

int trap(vector<int>& height)
{
    int left = 0, right = height.size() - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
            ++left;
        }
        else {
            height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
            --right;
        }
    }
    return ans;
}

Stack:

We keep a stack and iterate over the array. We add the index of the bar to the stack if bar is smaller than or equal to the bar at top of stack, which means that the current bar is bounded by the previous bar in the stack. If we found a bar longer than that at the top, we are sure that the bar at the top of the stack is bounded by the current bar and a previous bar in the stack, hence, we can pop it and add resulting trapped water to ans.

int trap(vector<int>& height)
{
    int ans = 0, current = 0;
    stack<int> st;
    while (current < height.size()) {
        while (!st.empty() && height[current] > height[st.top()]) {
            int top = st.top();
            st.pop();
            if (st.empty())
                break;
            int distance = current - st.top() - 1; //注意distance的作用
            int bounded_height = min(height[current], height[st.top()]) - height[top];
            ans += distance * bounded_height;
        }
        st.push(current++);
    }
    return ans;
}