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

示例：

输入：[3,1,2,5,2,4]

返回值：5

说明：数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，使用图形解释如下：

相信每个人都知道木桶原理，就是说一只木桶能盛多少水并不取决于桶壁上最长的那块木板，而恰恰取决于最短的那块。通过类比发现，每一根柱子所能承受的雨水=其左侧最高柱子与右侧最高柱子中的较小值-其自身柱子高度。因此最直接的办法是通过循环遍历数组arr，例如arr[i]，找到数组中arr[i]左侧最大值与右侧最大值中的较小值m，则第i个柱子所能承受的雨水=m-arr[i]，最后将所有的结果相加，然后这种方法由于存在双层循环，时间复杂度大大提升。在每一次寻找arr[i]的左侧最大值与右侧最大值，可能会存在重复寻找的问题，因此我们可以想到定义二维数组将arr每一个变量左右两侧的最大值保存，从而减少计算。步骤如下：

• 定义二维数组$dp[n][2]$,其中$dp[i][0]$用于保存arr[i]左侧柱子的最大值，$dp[i][1]$用于保存arr[i]右侧柱子的最大值。

• 寻找arr[i]左侧柱子的最大值可以直接使用arr[i-1]左侧柱子的最大值，其值已经保存在$dp[i-1][0]$中，从而减少循环计算

• 寻找arr[i]右侧柱子的最大值可以直接使用arr[i+1]右侧柱子的最大值，其值已经保存在$dp[i+1][0]$中，减少循环计算

• 每一个柱子的雨水量=其左侧最高柱子与右侧最高柱子中的较小值-其自身柱子高度

给定数组arr[6]={3,1,2,5,2,4}

arr[i]	3	1	2	5	2	4
左侧最大值$dp[i][0]$	3	3	3	5	5	5
右侧最大值$dp[i][1]$	5	5	5	5	4	4
雨水为$min(dp[i][0],dp[i][1])-arr[i]$	0	2	1	0	2	0
总的雨水	5

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
       long n = arr.size();
        if (n == 0)
        {
            return 0;
        }
        long res = 0;
        vector<vector<int> > dp(n); //定义二维数组，其中dp[i][0]用于保存arr[i]左侧柱子的最大值，dp[i][1]用于保存arr[i]右侧柱子的最大值。
        for(int i=0;i<n;i++)
        {
            dp[i].resize(2);
        }
        dp[0][0] = arr[0];//左侧第一个柱子的左侧柱子最大值为本身
        dp[n-1][1] = arr[n-1];//右侧第一个柱子的右侧柱子最大值为本身
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], arr[i]);//寻找arr[i]左侧柱子的最大值可以直接使用arr[i-1]左侧柱子的最大值，其值已经保存在dp[i-1][0]中
        }
        for (int i = n - 2; i >= 0; i--)
        {
            dp[i][1] = max(dp[i + 1][1], arr[i]);//寻找arr[i]右侧柱子的最大值可以直接使用arr[i+1]右侧柱子的最大值，其值已经保存在dp[i+1][0]中
        }
        for (int i = 0; i < n; i++)
        {
            res += min(dp[i][0], dp[i][1]) - arr[i];//每一个柱子的雨水量=其左侧最高柱子与右侧最高柱子中的较小值-其自身柱子高度
        }
        return res;
     }
    int max(int a,int b)
    {
        return (a>b?a:b);
    }
    int min(int a,int b)
    {
        return (a>b?b:a);
    }
};

• 时间复杂度:代码中使用四次单层循环遍历，，因此时间复杂度为$T(n)=O(3*n)$，总的时间复杂度为$O(n)$。

• 空间复杂度：使用了一个n×2的二维数组，因此空间复杂度为$O(n)$。

在上面的方法中，在计算arr[i]左侧柱子最大值与右侧柱子最大值时，使用了两次循环，即从左到右的循环和从右到左的循环，由此我们可以想到链表中的双指针，即通过设置双指针的办法，通过指针的移动，从而计算每个柱子可存储的水量，直到两个指针相遇。具体步骤如下：

• 初始化左侧柱子最大值left_max=arr[0]，右侧柱子最大值right_max=arr[n-1]

• 设置左侧指针为left，初始化为0，指向第一个柱子，向右移动

• 设置右侧指针为right,初始化为n-1，指向最后一个柱子向左移动

• 两个指针还未相遇时：

     • 如果左侧柱子最大值left_max小于右侧柱子最大值，并且left_max大于arr[left]，则可以计算当前左侧柱子的雨水，即为left_max-arr[left]，否则将更新left_max的值为arr[left]。之后left向右侧移动

     • 如果左侧柱子最大值left_max大于右侧柱子最大值，并且right_max大于arr[right]，则可以计算当前右侧柱子的雨水，即为right_max-arr[right]，否则将更新right_max的值为arr[right]。之后right向左侧移动

• 当两个指针相遇时即为运行结束的条件，此时左右柱子的雨水都已计算完。

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        int  n = arr.length;
        if(n == 0)
        {
            return 0;
        }
        long res = 0;
        int left = 0, right = n - 1;
        int left_max = arr[0], right_max =arr[n-1];
        while(left <= right)
        {
            if (left_max < right_max)//左侧柱子最大值left_max小于右侧柱子最大值
            {
                if (left_max > arr[left])//left_max大于arr[left]
                {
                    res +=left_max-arr[left];//计算当前左侧柱子的雨水
                }
                else 
                    left_max = arr[left];
             left++;
            }
            else//左侧柱子最大值left_max大于右侧柱子最大值
            {
                if (right_max > arr[right])//right_max大于arr[right]
                {
                    res+=right_max-arr[right];//计算当前右侧柱子的雨水
                }
                else
                {
                    right_max=arr[right];
                }
             right--;
            }
        }
       return res;
    }
    
}

复杂度分析

• 时间复杂度：单层循环，时间复杂度为$O(n)$

• 空间复杂度:  使用了几个变量作为指针，因此空间复杂度为$O(1)$