[LC]24.接雨水

题目

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

分析

暴力

对于每个位置 i ，分别找到其左右的最大高度$leftMax$和$rightMax$，那么该点能接的雨水值为$min(leftMax, rightMax) - height_i$.

时间复杂度: $O(n^2)$

动态规划

观察暴力算法，我们不难发现，时间复杂度高的原因主要是因为对于每个位置，寻找其左右的最大值需要$O(n)$的时间复杂度，我们可以用数组$leftMax$来维护每个位置左边的最大值，这样在遍历的时候只需要$O(1)$就能找到其左边的最大值，对于右边的最大值同理。

为了求得每个位置左边的最大值，规定$leftMax[i]$表示位置$i$左边的最大值，由此可以得到状态转移方程：
$$
\begin{align}
& leftMax[i] = max(leftMax[i - 1], height[i]) \\
& rightMax[i] = max(rightMax[i + 1], height[i])
\end{align}
$$
我们只需要从前往后遍历一遍数组，就可以得到$leftMax$，从后往前遍历一遍数组，就可以得到$rightMax$.时间复杂度为$O(n)$.

代码

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> leftMax(n, height[0]);
        vector<int> rightMax(n, height[n - 1]);
        for (int i = 1; i < n; ++i)
        {
            leftMax[i] = max(leftMax[i - 1], height[i]);
            rightMax[n - i - 1] = max(rightMax[n - i], height[n - i - 1]);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i)
        {
            ans += (min(leftMax[i], rightMax[i]) - height[i]); 
        }
        return ans;
    }
};

时间复杂度：$O(n)$

空间复杂度：$O(n)$

双指针

观察动态规划算法，我们可以发现，$leftMax$和$rightMax$数组是单调的，而且每个位置$i$的能接的雨水只取决于左边和右边最大值中较小的一个。如果我们使用双指针来做，边遍历边维护左右最大值。左指针指向的位置的左边最大值就是当前位置$i$的左边的最大值，右指针指向的位置的右边最大值就是当前位置$i$的右边的最大值。即，左指针的左边最大值是确定的，而右边的最大值有可能会增大，右指针的右边最大值是确定的，而左边的最大值可能会增大。此时，如果左边的最大值小于右边的最大值，那么左指针指向位置的值就可以计算了，因为其只取决于左边的最大值，如果右边的最大值小于左边的最大值，那么右指针指向位置的值就可以计算了。

代码

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n - 1;
        int leftMax = height[0], rightMax = height[n - 1];
        int ans = 0;
        while (left <= right)
        {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (leftMax <= rightMax)
                ans += (leftMax - height[left++]);
            else 
                ans += (rightMax - height[right--]);
        }
        return ans;
    }
};

时间复杂度：$O(n)$

空间复杂度：$O(1)$

单调栈

用一个单调栈来维护数组下标，保证靠近栈底的高度不小于靠近栈顶的高度。当遇到一个位置$i$的高度大于栈顶高度的时候，当前位置$i$，栈顶的位置$top$，栈顶第二个位置$left$，三者就可能构成一个凹槽，能够接雨水($height[left] >= height[top], height[i] > height[top], left < top < i$).接的雨水量等于$(min(height[left], height[i]) - height[top]) \times (i - left - 1)$.

代码

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> s;
        int ans = 0;
        for (int i = 0; i < height.size(); ++i)
        {
            while (!s.empty() && height[s.top()] < height[i])
            {
                int top = s.top(); s.pop();
                if (s.empty()) break;
                int left = s.top();
                ans += ((min(height[left], height[i]) - height[top]) *
                        (i - left - 1));
            }
            s.push(i);
        }
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.