LeetCode: L42接雨水_双指针方法

  |   0 评论   |   1,038 浏览

题目: https://leetcode-cn.com/problems/trapping-rain-water/
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水.

todo: 本来想用 markdown画个直方图来示意我的算法过程的. 找了半天好像实现不了. 后面再看看.先用官方的图试试:
L42PIC1.png
数组:[ 0 , 1 , 0 , 2 , 1 , 0 , 1, 3, 2, 1, 2, 1 ]

朴素解法

  1. 初始化slow=0 , fast = slow +1
  2. 判定slow 是否可以确定为左挡板 执行点1
    1. E1: 如果(data[slow] <= data[fast]). 执行: 左挡板往右移一格 slow=slow+1, fast=slow+1 , 回到:执行点1
      (注: 右边的数组没有形成递减趋势.至少当前的左档板不是最适合的适合的左档板.)
    2. E2: data[slow] > data[fast] 到 [3] (这个左档板是有可能是一个可接雨水的`左档板.)
  3. fast 往右移.直到找到: data[fast] >= data[slow] 或者没有找到: fast == array.length
    1. 找到. 把记录的此段积水值加到总和. slow = fast;fast = slow +1 回到执行点: [2]
    2. 没有找到. slow = slow+1; fast=slow+1 , 回到执行点: [2]
  4. 步骤 [3] 中的 slow越界到这里.结束.

代码

class Solution {
    public int trap(int[] height) {
        if(height.length <= 1){
            return 0;
        }
        int slow = 0;
        int fast = 1;
        int length = height.length;

        // 迭代条件
        // 初始化: slow,fast 初始化为起始位置

        // 如果下一个位置不低于当前.                                        slow=slow+1,fast=slow+1;
        // 如果下一个位置低于当前. ---> 开始计算雨水.
        // 计算过程中: 直到发现比起始高(包含 = ),此次计算结束. ==> 接的雨水相加. slow=fast, fast = slow+1
        //           没有发现比此高,放弃计算.                               slow 加一, fast = slow+1


        int sum = 0;

        // 终止条件: slow 
        while( slow < length - 2 ){
            if(height[slow+1]>=height[slow]){
                slow++;
                fast= slow+1;
                continue;
            }

            int tmpSum = 0;
            while((fast<= length-1) && height[fast]< height[slow]){
                tmpSum += height[slow]- height[fast];
                fast++;
            }
            if(fast<= length-1){
                sum += tmpSum;
                slow = fast;
                fast = slow + 1;
                continue;
            }else{
                slow += 1;
                fast = slow +1;
                continue;
            }
        }

        return sum;

    }
}

<I>注:对于可能的右结束不为 >=左挡板的情况当时可以移动 左挡板往右.因为这一段是递减的,定可能降低左档板以期达到左右两挡板相等的情况.比如: [5,4,2,4] 左挡板为5的时候.一直到右边结束的时候都找不到5的 右挡板,此时可以移动 左挡板到 4,这样就可以得到 [4, 2, 4] 可以计算出积水为 2. 但是实际存在 <font color='red'>一种例外的情况: 如 [5,4,2,3] 可以变为: [4,2,3] 这没问题 ,但是继续往下就是 [2, 3],最终错过 [4,2,3] 这个可能的积水为1的部分 </font></I>

改进代码

class Solution {
    public int trap(int[] height) {
        if(height.length <= 1){
            return 0;
        }
        int slow = 0;
        int fast = 1;
        int length = height.length;

        // 迭代条件
        // 初始化: slow,fast 初始化为起始位置

        // 如果下一个位置不低于当前.                                        slow=slow+1,fast=slow+1;
        // 如果下一个位置低于当前. ---> 开始计算雨水.
        // 计算过程中: 直到发现比起始高(包含 = ),此次计算结束. ==> 接的雨水相加. slow=fast, fast = slow+1
        //           没有发现比此高,放弃计算.                               slow 加一, fast = slow+1

        int sum = 0;

        // 终止条件: slow 
        while( slow < length - 2 ){
            if(height[slow+1]>=height[slow]){
                slow++;
                fast= slow+1;
                continue;
            }
            int tmpSum = 0;
            int secondHigh = height[fast];
            int secondIndex = fast;
            while((fast<= length-1) && height[fast]< height[slow]){
                if(secondHigh<= height[fast]){
                    secondHigh = height[fast];
                    secondIndex = fast;
                }
                tmpSum += height[slow]- height[fast];
                fast++;
            }



            if(fast <= length-1){
                sum += tmpSum;
                slow = fast;
                fast = slow + 1;
                continue;
            }else{

                // 需要反算:
                tmpSum = 0;
                int offset = -1;
                while((secondIndex+offset) >= slow+1){
                    tmpSum += height[secondIndex] - height[secondIndex+offset];
                    offset--;
                }

                sum += tmpSum;
                slow = secondIndex;
                fast = slow +1;

                continue;
            }
        }

        return sum;
    }
}

最终优化

这个效率不高之处是在于. 如果右边找不到比左边高的时候.这个时候 slow的步进是1这个效率是有些低. 好在能完成. 但是由于如上的4,2,3这样的序列会有遗漏,导致需要从3开始往回反算.这样会算两次. 实际上从左边开始往右找不到比左大的数的时候, 如果是从右边开始算的话就可以满足这样的条件.(递增)从而就可以避免算两次.

解题过程
  • 初始化 left和right分别为数组的左边界和右边界.
  • 判定两边界哪边小.从小的一边往大的一边推进. 这样一定能找到一个比此边界大(至少不小)的数.
  • 找到上面所说的另外一个边界的同时,可以计算出此段可接的雨水.
  • 同时在上面计算完雨水后, 相应的边界指针移动到计算接雨水的另外一个边界处.这样就可以缩小数组范围.回到第一步. 直到 left>=right 时.结束.

代码:

class Solution {
    public int trap(int[] height) {
        if(height.length <3){
            return 0;
        }

        int left = 0;
        int right = height.length - 1;
        int sum = 0;

        while(left < right){
            if(height[left] <= height[right]){
                // visit from left
                int tmpSum = 0;
                int tmpIndex = left +1;
                while(height[tmpIndex]< height[left]){
                    tmpSum += height[left] - height[tmpIndex];
                    tmpIndex++;
                }
                // for next calc
                sum += tmpSum;
                left = tmpIndex;
            }else{
                // visit from right
                int tmpSum = 0;
                int tmpIndex = right - 1;
                while(height[tmpIndex] < height[right]){
                    tmpSum += height[right] - height[tmpIndex];
                    tmpIndex--;
                }
                // for next calc
                sum += tmpSum;
                right = tmpIndex;
            }
        }
        return sum;
    }
}

算法解释:

  • 前面最开始我们确定了从左往右的方法,每个左挡板的高度,一直往右找到一个 >= 此高度的右挡板这一部分的雨水可以优先计算出来. 计算完成后可以把这一部分的数字去掉(trim). 这样就可以得到一个新的数组.至于为什么能trim是因为左边的挡板积的雨水是已经计算出来. 有与没有都不影响右边的值的计算.
  • 在去掉左边的挡板的时候, 不能把右挡板也去掉.因为右挡板有可能作为计算右边积水的左挡板.
  • 上面的描述是基于从左往右找的. 如果从右往左找反过来即可.
  • 至于为什么需要判定是从左往右还是从右往左.是为了一定能找到一个比左挡板高的右挡板.这样才可以完成这一部分的雨水计算.从而trim掉. 否则就会像上面的算法一样. 需要反过来计算.

评论

发表评论


取消