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.

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

解法1

这道题给出一个数组,每个元素是一个宽为1的bar,问这些bar组成的图行最多能装多少水,就是图上蓝色的部分.如果当前位置高度大于两边的高度,我们就认为当前位置对结果有贡献.当前位置的贡献值,为左边高度的最大值和右边高度的最大值,取其中最小的和当前的高度相减.

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

解法2

使用栈来求解.遍历高度,如果栈为空或者当前高度小于栈顶高度则把当前高度的坐标压入栈.当遇到比栈顶高度大的高度时,说明有坑存在.此时栈里至少有一个高度,如果只有一个的话,那么不能形成坑,跳过.如果大于一个的话,那么此时把栈顶元素取出来当做坑,新的栈顶元素就是左边界,当前高度就是右边界,只要取二者较小的,减去坑的高度,长度就是右边界减去左边界坐标再减1,二者相乘就是该坑的水量.

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int i = 0,n = height.size(),res = 0;
        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;
                res += (min(height[i],height[st.top()])-height[t]) * (i-st.top()-1);
            }
        }
        return res;
    }
};

资料

https://blog.csdn.net/viewsky11/article/details/80571413

https://leetcode.com/problems/trapping-rain-water/discuss/17364/7-lines-C-C++

http://www.cnblogs.com/grandyang/p/4402392.html

 
comments powered by Disqus