题解 | #接雨水问题#

题意：

• 将一个数组看成柱子高度，求柱子组成的容器最多能装的水的量。

方法一：

• 记录左侧最高柱子以及右侧最高柱子，蓄水的条件是两侧的高度取较小的值。因此取两者的较小值，减去当前值即为接雨水的值。

  图解如下：

• 输入： [3,1,2,5,2,4]
  红色线表示左侧最高柱子，黄色线表示右侧最高柱子，黄色部分表示两者最小值构成的区域，紫色部分表示装水值。
• 结果：5

代码如下：

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
        vector<int> leftStart,rightStart;
        int maxHeight=arr[0],n=arr.size();
        //从左向右不减的数组，表示左侧最高柱子
        for(int i=0;i<n;i++){
            maxHeight=max(arr[i],maxHeight);
            leftStart.push_back(maxHeight);
        }
        //从右向左不减的数组，表示右侧最高柱子
        maxHeight=arr[n-1];
        for(int i=n-1;i>=0;i--){
            maxHeight=max(arr[i],maxHeight);
            rightStart.push_back(maxHeight);
        }
        //利用三个数组的关系计算得到结果
        long long ans=0;
        for(int i=0;i<n;i++){
            //蓄水的条件是满足短板，即左右侧最高柱子的较小值。
            ans+=min(leftStart[i],rightStart[n-1-i])-arr[i];
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：，n为数组arr长度，遍历数组常数次。
空间复杂度：，额外的两个长度为n的数组leftStart,rightStart。

方法二：

• 使用单调递减栈，一层一层的计算接雨水的量。如题目中的图所示：
  
• 用一个单调递减栈从左往右存柱子的高度。如上图应该前两个元素是3,1。第三个元素是2，不符合单调递减栈的要求，如果栈中的元素大于等于两个，在此处就是3,1。3,1,2组成了一个容器，该容器的蓄水量是。同理遍历至下一个则是。

代码如下：

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
        long long ans=0,cur=0;
        //栈s存的是数组arr的下标
        stack<int> s;
        while(cur<arr.size()){
            //当前元素不满足单调递减栈的要求，求组成的容器的蓄水量
            while(!s.empty()&&arr[s.top()]<arr[cur]){
                int last=s.top();
                s.pop();
                //栈中的元素只有一个，不能组成蓄水的条件
                if(s.empty())
                    break;
                //计算当前求的蓄水的长度和宽度
                long long length=cur-s.top()-1;
                long long height=min(arr[cur],arr[s.top()])-arr[last];
                ans+=length*height;
            }
            //当前元素满足单调递减栈的要求，直接入栈
            s.push(cur++);
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：，n为数组arr长度，遍历数组一次，每个元素出入栈操作共两次 。
空间复杂度：，单调递减栈的最大空间要求n。

方法三：

• 对方法一的leftStart，rightStart数组，其目的是用于记录左侧和右侧最大值。可以使用两个变量来替代，以此降低空间复杂度。
• 双指针left，right分别从左向右和从右向左移动，leftMax，rightMax分别记录左侧最大值和右侧最大值。leftMax<rightMax时，则雨水取决于左，那么计算leftMax-arr[left]值即为接雨水的量，反之类似。while循环直到left>=right，遍历数组arr，返回结果ans。

  class Solution {
  public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
        long long ans=0;
        int left=0,right=arr.size()-1;
        //利用两个变量leftMax,rightMax来记录左右柱子的最大值
        int leftMax=arr[left],rightMax=arr[right];
        while(left<right){
            //左高度小于右高度，则雨水取决于左，否则取决于右。
            if(leftMax<rightMax){
                //计算接雨水的值并更新left和leftMax
                ans+=leftMax-arr[left];
                left++;
                leftMax=max(leftMax,arr[left]);
            }else{
                //计算接雨水的值并更新right和rightMax
                ans+=rightMax-arr[right];
                right--;
                rightMax=max(rightMax,arr[right]);
            }
        }
        return ans;
    }
  };

  复杂度分析：

  时间复杂度：，遍历数组arr。
  空间复杂度：，常数个临时变量。