题解 | #接雨水问题#

一.题目描述
NC128接雨水问题
给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：[3,1,2,5,2,4]
返回：5
二.算法(双指针)

使用两个指针，一个l_max,一个r_max：
首先每次循环开始，先获取l的左边 [0, l-1]最高柱子高度和r右边[r+1,len-1]最高柱子高度（都不包括l和r本身）
(1)当l_max<r_max时，那么就说明对于l右边一定有比l_max更高的柱子，那么只需要判断l左边 最高柱子l_max 是否比l柱子高就行了，如果是，那么就能装水
(2)当l_max>=r_max时，那么就说明对于r左边一定有比r_max更高或者相同高度的柱子，那么只需要判断r右边最高柱子r_max是否比r柱子高就行了
下面是通过代码：

class Solution {
public:
    long long maxWater(vector<int>& arr) {
        int len=arr.size();
        if(len<=2) return 0;
        int l=0,r=len-1;
        int m=min(arr[l],arr[r]);
        long long int sum=0;
        // 找出左右边界的最小值作为水位高度
        while(l<r){
            if(arr[l]<arr[r]){
                l++;
                // 如果当前标尺小于水位，则水量累加
                if(arr[l]<m){
                    sum+=m-arr[l];
                } else { // 否则，将此标尺和右边边界高度进行比较，找出剩下数组中的新水位
                    m=min(arr[l],arr[r]);
                }
            } else {
                r--;
                // 同理，如果当前标尺小于水位，则水量累加
                if(arr[r]<m){
                    sum+=m-arr[r];
                } else {
                    // 否则，将此标尺和左边界的高度进行比较，找出剩余数组中的新水位
                    m=min(arr[r],arr[l]);
                }
            }
        }
        return sum;
    }
};

时间复杂度：。只遍历了一遍数组。
空间复杂度：。使用了有限的 left, right, ans, maxleft, maxright。
优缺点：空间复杂度低，但是代码实现比较麻烦
三.算法(单调栈)

除了计算并存储两个位置两边的最大高度以外，也可以利用单调栈计算能接到的雨水总量。维护一个单调栈，单调栈存储的下标，满足从栈底到栈底的下标对应的数组height中的元素递减。
下面是完整代码:

class Solution {
public:
    long long maxWater(vector<int>& arr) {
        long long int ans=0;
        stack<int>st;
        int n=arr.size();
        for(int i=0;i<n;i++){
            while(!st.empty()&&arr[i]>arr[st.top()]){
                int top=st.top();
                st.pop();
                //盛水的水底，用过了就要pop出来
                if(st.empty()) break;
                //栈中元素没有底了 就直接结束
                long long int left=st.top();
                long long int width=i-left-1;
                long long int height=min(arr[left], arr[i])-arr[top];
                ans+=width*height;
            }
            st.push(i);
        }
        return ans;
    }
};

时间复杂度：，其中n是数组arr的长度。
空间复杂度：，其中n数组arr的长度。空间复杂度主要取决于栈空间，栈的大小不会超过n。
优缺点：空间复杂度高，但是代码实现简单