[数据结构与算法]Leetcode42 接雨水

看到这个题我的第一反应就是使用暴力+动态规划，从左到右依次确定每个位置左右两边的最高值（leftmax和rightmax），至于怎么确定这里就用到了动态规划: 创建两个数组分别储存leftmax和rightmax（动态规划一般都要创建数组，以空间换时间）.
leftmax的确定: 令leftmax[0] = height[0],然后从1开始正向遍历数组，通过Math.max(leftmax[i-1],height[i])，依次确定各个位置的leftmax。
rightmax同理令rightmax=height[i-1],从反向开始遍历。
最高值确定以后用Max.min(leftmax,rightmax)-height[i]这个公式就可以算出能接多少雨水

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if(n<2)  return 0; 
        int[] leftmax = new int[n];
        leftmax[0] = height[0];
        for(int i = 1; i <n; i++){
            leftmax[i] =Math.max(leftmax[i-1],height[i]);
        } 
        int[] rightmax = new int[n];
        rightmax[n-1] = height[n-1];
        for(int i =n-2 ; i>=0; i--){
            rightmax[i] = Math.max(rightmax[i+1], height[i]);
        } 
        int ans = 0;
        for(int i=0;i < n; i++){
            ans+= Math.min(leftmax[i],rightmax[i]) - height[i];
        }
        return ans;
    }
}

双指针

双指针法相较于动态规划空间复杂度更小，是O(1)级别的。我们只需要创建两个指针 l指针和 r指针 ，l指针只向左，r指针只向右。这样会出现四个变量l_leftmax 、l_rightmax 、r_leftmax 、r_rightmax。但实际上我们只需要维护 l_leftmax 和 r_rightmax 这两个变量即可，因为由于r>l，所以 l_leftmax <=r_leftmax ，l_rightmax > r_rightmax。 如果l_leftmax < r_rightmax ,则有l_leftmax < l_rightmax，所以l点可以接水，所以l点接的水就等于leftmax-height【l】，l指针++。反之 l_leftmax >= r_rightmax 则一定有 r_leftmax >=r_rightmax,r点可以接水，r点接的水等于rightmax - height【r】，r指针减减。从这我们就可以看到只需要判断l_leftmax 和 r_rightmax 这两个变量的大小就能确定该点是否能接水，能接多少水，所以我们只需要维护 l_leftmax 和 r_rightmax 这两个变量即可. 当两个指针 l和r对撞以后我们就可以确定能借多少水，就能得到我们想要的答案了

上面解释为什么只需要维护两个变量 l_leftmax 和 r_rightmax时由于使用的字母太多了，所以接下来再用图像解释一番。

class Solution {
    public int trap(int[] height) {
        int n = height.length,ans = 0;
        int l=0, r=n-1;    //确定l，r两个左右指针
        int l_leftmax = 0,r_rightmax = 0;
        while(l<r){
            l_leftmax = Math.max(l_leftmax,height[l]);
            r_rightmax = Math.max(r_rightmax,height[r]);
            if(l_leftmax < r_rightmax){
                ans +=l_leftmax - height[l];
                l++;
            }else{
                ans +=r_rightmax - height[r];
                r--;
            }
        }
        return ans;
    }
}