42.Trapping Rain Water¶

42.Trapping Rain Water¶

Tags: Hard Stack Array Two Pointer

Links: https://leetcode.com/problems/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

Answer:

方法一：双指针法。

每个元素能接的雨水量是：当前位置左边最高的数与右边最高的数的最小值减去当前位置的数。

例如第六个元素接水量为2 = min(2,3)-0=2。

对于每个位置，都考虑其左边最高的墙和右边最高的墙即可。

上述思路需要额外考虑一下左右边界，记得84.Largest Rectangle in Histogram题目里需要在尾端添加一个0元素来作为结尾。本题有个隐藏的特点就是，无论什么情况，左右边界都无法盛水。如果数组下标是从0——(n-1)，那么我们需要考虑的下标范围只是从1——(n-1-1)。

问题集中在如何去寻找当前位置的左右最高墙。以题目中给出的例子来讲，数组大小n = 12，实际上最后去寻找最高墙只关心1——11这些位置。程序的第9、10行可以理解成一种递归：对于第i个位置，我们去观察它最邻近的左边的位置i-1，如果i-1的左边墙低于i-1的高度，那么可以认为i-1的高度是一个局部顶峰，所以自然就是i的左边墙，右边墙同理。15——18相当于对**“当前位置左边最高的数与右边最高的数的最小值减去当前位置的数”**的翻译。

//时间复杂度O(n)， 空间复杂度O(n)
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> max_left(n, 0);
        vector<int> max_right(n, 0);

        for (int i = 1; i < n; ++i){
            max_left[i] = max(max_left[i - 1], height[i - 1]);
            max_right[n - i - 1] = max(max_right[n - i], height[n - i]);
        }

        int sum = 0;

        for (int i = 0; i < n; ++i){
            int h = min(max_left[i], max_right[i]);
            if (h > height[i])
                sum += h - height[i];
        }

        return sum;
    }
};

方法二：找最高墙

找到数组中最高的墙，把数组分成左右两半，分别处理。思路和双指针有异曲同工之处，区别在于，双指针总是找左右最邻近的墙；找最高墙是对于左边的序列，右边墙已经找到，只需要找左边的墙，对于右边序列，左边墙已经找到，只需要找右边墙。

//时间复杂度O(n)， 空间复杂度O(1)
class Solution {
public:
    int trap(vector<int>& height) {
        int sum = 0;
        int max = 0;

        for (int i = 0; i < height.size(); ++i){
            if (height[i] > height[max])
                max = i;
        }

        for (int i = 0, top = 0; i < max; ++i){
            if (height[i] > top) top = height[i];
            else sum += top - height[i];
        }

        for (int i = height.size() - 1, top = 0; i > max; --i){
            if (height[i] > top) top = height[i];
            else sum += top - height[i];
        }

        return sum;
    }
};

方法三：辅助栈法

class Solution {
public:
    int trap(vector<int>& height) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = height.size(); if (n <= 2) return 0;
        stack<int> s;
        int res = 0;
        int i = 0;
        while (i < n) {
            if (s.empty() || height[i] <= height[s.top()])
                s.push(i++);
            else {
                int bottom = height[s.top()]; s.pop();
                if (s.empty()) continue;
                res += (min(height[i], height[s.top()]) - bottom) * (i - s.top() - 1);
            }
        }

        return res;
    }
};