聖地亞歌

Leetcode P0042"Trapping Rain Water" 题解

2020/08/23 Leetcode

博文中会简要介绍Leetcode P0042题目分析及解题思路。

“Trapping Rain Water”是一道非常经典的问题，在很多面试中都会出现，也属于原型题之一。这篇博文主要介绍动态规划的做法，比较简单直接。C++代码实现了使用栈（单调栈）的解法，有一些具体注释，这里不再赘述。使用栈的解法相对于用动态规划的解法，在思维上相对要复杂一些。

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.

下面重点讲解动态规划的思路。仔细读题后我们不难发现，想要得到以某一个bar为底座的储水量，需要知道这个bar左边最高的高度和右边最高的高度，然后取这两个高度中的较小值，用这个较小值与当前这个bar的高度作差就能得到这个bar为底座的储水量了。

为什么需要知道左右端的最大高度呢？

原因其实很简单，如果我们假定右端高度无穷大，那么左端的高度越高，以该bar为底座，宽度为1的上方的储水量也就越多，也就是说储水量取决于左端（也是较小端，因为右端高度是无穷大），同理右端，所以找到左右端最大高度。而实际的储水量则取决于这两个高度中的较小值，也是前面说到的取决于较小端。于是我们就得到了计算储水量的方法。

那么如何快速地得到左右两端的最大值呢？我们可以使用动态规划的思维，即一个bar左端的最大值一定等于这个bar前面一个bar的左端最大值和这个bar自身的高度中的较大值，也即：

    leftMax[i] = max(height[i], leftMax[i-1]);
Plaintext

这样一来我们就得到每个bar左端的最大高度，同理我们也可以得到每个bar右端的最大值，然后计算储水量，使用两端最大高度中的较小值作为实际水面即可。

以下是Java的题解代码实现。

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0)
            return 0;
        
        int[] cover = new int[height.length];
        int leftMax = height[0];
        for (int idx=1; idx<height.length; ++idx) {
            if (height[idx] > leftMax) {
                leftMax = height[idx];
            }
            
            cover[idx] = leftMax;
        }
        
        int rightMax = height[height.length-1];
        int trapped = 0;
        for (int idx=height.length-2; idx>0; --idx) {
            if (height[idx] > rightMax) {
                rightMax = height[idx];
            }
            
            trapped += (Math.min(rightMax, cover[idx])-height[idx]);
        }
        
        return trapped;
    }
}
Java

以下是实现了单调栈解法的C++题解代码实现。

class Solution {
public:
    int trap(vector<int>& height) {
        int trapped_water = 0, current = 0;
        stack<int> st;
        while (current < height.size()) {
            // 若栈顶bar高较大，则将当前较小bar塞入栈中，成为底座；反之则开始计算储水量
            // 如果栈非空，并且栈顶小于当前bar高，则有装水可能，寻找到最左边的bar直到栈空或者栈顶更高
            while (!st.empty() && height[current] > height[st.top()]) {
                int top = st.top();
                st.pop();
                // 若栈空说明左端bar已经出栈，没有左端bar拦水，则不用再计算储水量
                if (st.empty())
                    break;
                
                // 计算当前bar的位置到左端bar位置的宽度
                int distance = current-st.top()-1;
                // 计算当前左右端的bar所限定的区域内的水面高度和当前底座高度的差
                int bounded_height = min(height[current], height[st.top()]) - height[top];
                trapped_water += distance * bounded_height;
            }
            
            st.push(current);
            ++current;
        }
        
        return trapped_water;
    }
};
C++

Search