LeetCode.42 接雨水

记录了一道经典笔试题的三种解法。

单调栈

利用单调栈，在每次将柱子压入栈之前，计算栈中要弹出的柱子与当前柱子之间的雨水面积，以及栈顶的柱子与当前柱子之间的雨水面积并求和。

class Solution {
public:
    int stk[20010], tt = 0;
    int trap(vector<int>& height) {
        int res = 0;
        for (int i = 0; i < height.size(); i ++) {
            int last = 0;
            while (tt && height[stk[tt]] <= height[i]) {
                res += (height[stk[tt]] - last) * (i - stk[tt] - 1);
                last = height[stk[tt]];
                tt --;
            }
            if (tt) res += (height[i] - last) * (i - stk[tt] - 1);
            stk[++ tt] = i;
        }
        return res;
    }
};

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

动态规划

对于每一个柱子$i$，雨水能达到的最大高度为$i$两边最大高度$l_{max}$和$r_{max}$的较小值，即$\min(l_{max},r_{max})$，故利用动态规划先计算每个点左右两边的最大值，再取它们的较小值，用它减去柱子的高度即可。

class Solution {
public:
    int max_left[20010], max_right[20010];
    int trap(vector<int>& height) {
        for (int i = 1; i < height.size(); i ++)
            l_max[i] = max(l_max[i - 1], height[i - 1]);
        
        for (int i = height.size() - 2; i >= 0; i --)
            r_max[i] = max(r_max[i + 1], height[i + 1]);

        int res = 0;
        for (int i = 1; i < height.size() - 1; i ++) {
            int h_min = min(l_max[i], r_max[i]);
            if (h_min > height[i])
                res += h_min - height[i];
        }
        return res;
    }
};

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

双指针

由于要求$\min(l_{max},r_{max})$，当求出$l_{max}$时，若右指针$r$的高度$height_{r}$大于左指针$l$的高度$height_{l}$，则左指针$l$的$r_{max}$已经不重要了，因为找出一个比$l_{max}$大的$height_{r}$，因此$\min(l_{max},r_{max})$必为$l_{max}$，故用其减去$height_{l}$即可求出当前柱子能接住的雨水，反之同理。

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int l_max = 0, r_max = 0;
        int res = 0;
        while (l < r) {
            l_max = max(l_max, height[l]);
            r_max = max(r_max, height[r]);
            if (height[l] < height[r]) res += l_max - height[l ++];
            else res += r_max - height[r --];
        }
        return res;
    }
};

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。