【算法速刷(9/100)】LeetCode —— 42.接雨水

目录

自我解法

官方解法

解法一：动态规划、前后缀

解法二：单调栈

自我解法

这道题刚拿到的时候，第一时间的想法是将其想象成MC一样的方块世界，如何去生成水一样的去解决。后来发现有点复杂化了，因为题目只需要累计的结果数字，不需要额外的东西，但因为先入为主的观念，我还是选择了从低到高从左到右依次遍历的模拟法，这种方法的复杂度基本上是O(N * MaxHeight)，实际也是十分低效，但私以为思路也是值得一分享，最后用例通过319/323。

class Solution {
public:
    int trap(vector<int>& height) {
        //从低到高从右向左打射线，找到间隔布置的两个方块，计算间隔，累加到结果上

        int res = 0;
        int n = height.size();
        int maxHeight = *max_element(height.begin(), height.end());
        
        for(int y = 1; y <= maxHeight; y++)
        {
            int lastBlockX = -1;
            for(int x = 0; x < n; x++)
            {
                if(height[x] >= y)
                {
                    if(lastBlockX != -1)
                    {
                        res += x - lastBlockX - 1;
                    }

                    lastBlockX = x;
                }
            }
        }

        return res;
    }
};

官方解法

官方的解法从数学角度考虑，并没有被这张图迷倒，而是在一维上解决问题，从这个角度出发，怎么也不会搞出来O(n * MaxHeight)的复杂度。

解法一：动态规划、前后缀

正所谓问题的关键在于找到关键的问题，这道题的关键也就是关键的问题：如何在数组的某个位置上计算其位置上能积累的水的高度？

实际上给定位置上能积水的高度就是“左边最高高度和右边最高高度”中的最小值。

我们可以通过构造两个数组来分别记录一个位置上左边和右边的最高高度，O(2N)的复杂度即可完成构造。注意构造的数组的值，不应低于当前位置的高度，假设左边高度始终低于当前高度，则在数组中记录为当前位置的高度，这样可以保证构造的数组减去原数组中当前位置高度不会出现负值。

最后指定一个位置，其能积累的水高度就是 min(leftMaxH, rightMaxH) - currentH

这个算式的值域 >= 0

最后时间复杂度即为O(3n) = O(n)，漂亮滴很呐

class Solution {
public:
    int trap(vector<int>& height) {
        //预处理每个方块的左边和右边的最大数
        //该区块的纵向存水数量为左右墙中最低的高度减去自身

        int n = height.size();

        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for(int i = 1; i < n; i++)
            leftMax[i] = max(leftMax[i - 1], height[i]);
        
        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; i--)
            rightMax[i] = max(rightMax[i + 1], height[i]);

        int res = 0;
        for(int i = 0; i < n; i++)
            res += min(leftMax[i], rightMax[i]) - height[i];
        
        return res;
    }
};

解法二：单调栈

除了上面比较常见的做法，还有就是使用单调栈。直观来说，通过维护一个单调递减的栈，可以通过进栈出栈来识别哪里是洼地，进栈则坡的方向是↘，出栈则坡的方向是↗。遇到递增则进行出栈操作，两个坐标之间的间隔必为空，即可以储水，累加到结果中。

需要注意的是，在出栈的操作中，需要三个高度

• 第一个高度（栈顶），代表需要忽略的高度，因为是上一次已经处理过的，不忽略会导致重复累加
• 第二个高度（次栈顶），代表当前蓄水的左边界高度，本次循环中不出栈，等下一次出栈。
• 第三个高度（当前遍历到的），代表当前蓄水的右边界高度，尚未入栈。

如果是第一次做的话，还是很难想到这样写的，Debug会疯掉哒

class Solution {
public:
    int trap(vector<int>& height) {
        
        stack<int> stk;
        int n = height.size();
        int res = 0;

        for(int i = 0; i < n; i++)
        {
            while(!stk.empty() && height[i] > height[stk.top()])
            {
                int top = stk.top();
                stk.pop();
                if(stk.empty())
                    break;

                int left = stk.top();
                int space = i - left - 1;
                int h = min(height[left], height[i]) - height[top];
                res += space * h;
            }
            stk.push(i);
        }

        return res;
    }
};