【每日一题】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.

img
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

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

题解

首先根据题目中给定的例子，进行分析。如果某根柱子可以盛水的话，必然是形成了“坑”，也就是说当前柱子的高度小于左边柱子的高度，也小于右边柱子的高度；如果我们可以知道每个柱子对应的左右高度，然后这两个高度取一个最小值，作为当前柱子如果可以形成“坑”对应的高度；然后用这个高度和柱子高度做减法，得到当前的水量，累加即可得到最终的结果。

所以，问题变成计算每个柱子形成“坑”的高度：可以使用动态规划的方法，声明一个数组dp，dp[i]为坑的高度；

计算过程，从左往右，计算当前柱子左边的柱子的最高值；从后往前，计算右边柱子的最高值，两个高度取最小值，作为最终的dp[i]，然后判断dp[i]与当前柱子高度height[i]的大小，如果dp[i]高，说明形成了坑，计算当前柱子的盛水量，累加到结果中；遍历完成后，返回累加和即可。

对应代码：

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

解法二：栈

遍历高度，如果栈为空，或者当前高度小于等于栈顶高度，则把当前高度的下标压入栈(而不是柱子的高度，使用下标方便计算形成的坑的长度)；如果当前高度大于栈顶元素，则弹出栈顶元素；如果弹出后，栈为空，说明弹出元素左边的柱子高度都小于等于它，形成不了坑，继续执行；如果栈不为空，那么取出来的栈顶元素作为坑，计算新的栈顶元素和当前高度的较小值，作为坑的高度，坑的宽度等于当前元素下标和新的栈顶元素下标相减再减1，高度和宽度相乘，得到坑可以盛水的量，然后累加到结果中。

代码：

cclass Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size(), i = 0, result = 0;
        stack<int> data;
        
        while (i < size){
            while (!data.empty() && height[i] > height[data.top()]){
                int t = data.top();
                data.pop();
                if (data.empty()) break;
                
                int distance = i - data.top() - 1;
                int bounded_h = min(height[i], height[data.top()]) - height[t];
                result += distance * bounded_h;
            }
            data.push(i++);
        }
        return result;
    }
};

reference

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

---

欢迎关注公众号，一起学习