【动态规划】 接雨水问题 JAVA全过程详解

【前言】：本文讲解【动态规划】及其改进版【双指针】，时间复杂度均为O(n)，空间复杂度前者为O(n)、后者为O(1)。

牛客版描述：给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图。计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度均视为0)
力扣版描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

1. 要求

数据范围：数组长度 0 <= n <= 2*10⁵，数组中每个值满足 0 < val <= 10⁹
要求：时间复杂度 O(n)

2. 样例

输入： arr = [3,1,2,5,2,4]
输出： 5

输入： arr = [0,1,0,2,1,0,1,3,2,1,2,1]
输出： 6

对于某个柱子arr[ i ]而言，计算它能接的水cap[ i ]其实只需要找它左边的最大值iLeft和右边的最大值iRight，这两个最大值就像木桶的两块木板把arr[ i ]夹在中间决定了cap[ i ]的上限，而具体能接到多少则取决于两者的最小值（短板效应），即　cap[ i ] = min ( iLeft , iRight )。

因此解题时只需要定义两个数组leftMax和rightMax，从左往右地遍历arr数组，找到每个arr[ i ]左边的最大值存入leftMax；再从右往左地遍历arr数组，找到每个arr[ i ]右边的最大值存入rightMax。最后再次遍历arr数组计算每个arr[ i ]的接水量，累加起来就是最终结果ret。

时间复杂度：O(n)　3次遍历数组
空间复杂度：O(n)　2个辅助数组

class Solution {
    public int trap(int[] arr) {
        // 找出每个arr[i]左边的最大值（包含它自己）
        int[] leftMax = new int[ arr.length ];
        leftMax[0] = arr[0];
        for ( int i=1; i=0; i-- )
            rightMax[i] = Math.max( rightMax[i+1], arr[i] );
            
        // 用max( iLeft, iRight) - arr[i]求出每个arr[i]的最大接水量
        int ret = 0;
        for ( int i=0; i 
三、改进版 - 双指针 
在动态规划中我们使用2个辅助数组存放iLeft和iRight，是为了方便我们比较iLfet和iRight的大小关系、判断出哪个才是决定arr[ i ] 接水量的短板。但事实上我们不用把这些值全部求出，使用【双指针】就能解决这一问题。现在定义一个指针 i 从左向右走，整型变量iLeft表示arr[ i ]左边的最大值；定义另一个指针 j 从右往左走，整型变量jRight表示arr[ j ]右边的最大值。
 
（下文中，凡是我们定义的两个变量 iLeft 和 jRight 都加粗显示，未定义的 iRight 和 jLeft 都加上删除线以作区分）
 
在 i 和 j 相遇以前，由于 i 在 j 的左边、i 左边的元素是 j 左边元素的子集，所以显然有 iLeft <= jLeft 。此时判断 iLeft 和 jRight 的大小关系，如果有 jRight <= iLeft ，那么根据不等式的传递性就一定有 jRight <= jLeft 。换言之，尽管我们只定义了 iLeft 和 jRight 这两个变量而没有求解 jLeft ，但仍然能通过 jRight <= iLeft 知道 jRight 是决定 arr[ j ] 接水量的那个短板。
 
同理，由于 j 在 i 的右边、j 右边元素是 i 右边元素的子集，有 iRight >= jRight 。如果判断出 jRight >= iLeft ，那就一定有 iRight >= iLeft 。我们即便不求 iRight 也能知道 iLeft 是决定 arr[ i ] 接水量的短板。
 
由此我们就有了解题思路，不断地更新 iLeft 和 jRight 并比较它们的大小关系，如果 iLeft >= jRight ，那 j 的接水量就可以计算 = jRight - arr[ j ]，然后将 j 指针左移一位；反之如果iLeft < jRight，那 i 的接水量就可以计算 = iLeft - arr[ i ]，然后将 i 指针右移一位。循环直到 i 和 j 相遇。
 
时间复杂度：O(n)　1次遍历数组
 空间复杂度：O(1)　4个整型变量
 
class Solution {
    public int trap(int[] height) {
        int ret = 0;
        int i = 0,      j = height.length-1 ;
        int iLeft = 0,  jRight = 0 ;
        while (i<=j)
        {
            iLeft  = iLeft  > height[i] ? iLeft  : height[i] ;
            jRight = jRight > height[j] ? jRight : height[j] ;
            if ( iLeft >= jRight )
                ret  += jRight-height[j--] ;
            else
                ret  += iLeft-height[i++] ;
        }
        return ret;
    }
}