接雨水 ， 给定二维图，能容多少水

42. 接雨水 - 力扣（LeetCode）

看着就是非常常规的题目，所以非常有必要掌握。

最少也把O（n^2）的方法写出来吧。力扣官方题解的三种方法O（n）都挺好，不过可能有点难读，在此经过学习，写一篇自己的通俗理解。

0.O(n^2）

每次只看单个格子，这个格子能放多少水呢？

只要左边和右边都比自己高，就能放水了。

所以对于每个格子，分别找到最左和最优最高的，（根据木桶原理。。）此格子能放的水就是较低的那个。

class Solution {
public:
    map<int,int>mm;
    int trap(vector<int>& height) 
    {
        int ret = 0;
        int n = height.size();
        for(int i=0;i<n-1;i++)
        {
            int r;
            int maxv = 0,maxo = 0;
            for(r=i+1;r<n;r++)
            {
                if(height[r]>=height[i])
                    break;

                if(height[r] >= maxv)
                {
                    maxv = height[r];
                    maxo = r;
                }
            }
            if(r>=n)
            {
                int aim = maxv;
                for(int j = i+1;j<maxo;j++)
                {
                    if(height[j]<aim)
                        ret += aim - height[j];
                }
                i = maxo-1;
            }
            else
            {
                int aim = min(height[i],height[r]);
                for(int j = i+1;j<r;j++)
                {
                    if(height[j]<aim)
                        ret += aim - height[j];
                }
                i = r-1;
            }
        }
        return ret;
    }
};

1.动态规划

其实跟背包问题差别蛮大的。

看题解这张图其实就很好懂：

左往右遍历一次，右往左遍历一次，取覆盖区域并集即可。（哇这是动归吗）

class Solution {
public:
    map<int,int>mm;
    int trap(vector<int>& height) 
    {
        int n = height.size();
        vector<int>l(n),r(n);
        int tmp = 0;
        for(int i=0;i<n;i++)
        {
            tmp = max(tmp,height[i]);
            l[i] = tmp;
        }
        tmp = 0;
        for(int i=n-1;i>=0;i--)
        {
            tmp = max(tmp,height[i]);
            r[i] = tmp;
        }
        int ret = 0;
        for(int i=0;i<n;i++)
        {
            ret += min(l[i],r[i]) - height[i];
        }
        return ret;
    }
};

2.单调栈

是这样的一个解法。

如果多格高：

单调栈内放下标，他们的高度 从栈底到栈顶 是降低的。

直到遇见一个高的，那么栈顶的就可以作底去装水，高度为左边和右边较低者。

class Solution {
public:
    stack<int>sti;
    int trap(vector<int>& height) 
    {
        int n = height.size();
        int ret = 0;
        for(int i=0;i<n;i++)
        {
            while(sti.size()&&height[i] > height[sti.top()])
            {
                //这个是放水的平面
                int top = sti.top(); sti.pop();
                if(sti.size() == 0)break;//挨着的 | 上升的

                //补的是和左边这个高度差

                ret += (i-sti.top()-1) * (min(height[sti.top()],height[i]) - height[top]);
            }            
            sti.push(i);
        }
        return ret;
    }
};

3.双指针

和1类似，是对0的优化，不用每次都挨着找一遍。官方题解写法我看不太懂。但思想是明确的。

我们找左边最大 leftmax和右边最大 rightmax，那么中间就是容器能装水啦。

我们从低的一边向另一边走，遇到的格子能放的水都最多到低的这边的高度。

比如 leftmax <= rightmax ，左向右，每个格子都能装水到 leftmax。

直到遇见高边，且这个高边比右边最高还高，就可以从右向左了。

不然就一直往右装水：

class Solution {
    //其实右边有足够高的，左边底的绝对都能放进去水
public:
    int trap(vector<int>& height) 
    {
        int n = height.size();
        int l = 1,r = n-2;
        int leftmax = height[0],rightmax = height[n-1];
        int ret = 0;
        while(l<=r)
        {
            while(leftmax <= rightmax&&l<=r)
            {
                if(height[l] < leftmax)
                    ret += leftmax - height[l];
                else
                    leftmax = height[l];
                l++;
            }
            
            while(leftmax > rightmax&&l<=r)
            {
                if(height[r] < rightmax)
                    ret += rightmax - height[r];
                else
                    rightmax = height[r];
                r--;
            }
        }
        return ret;
    }
};