[Leetcode] Trapping Rain Water 积水问题

caohaoyu 发布于2019-08-14 12:29 / 2408人阅读

摘要：从右向左遍历时，记录下上次右边的峰值，如果左边一直没有比这个峰值高的，就加上这些差值。难点在于，当两个指针遍历到相邻的峰时，我们要选取较小的那个峰值来计算差值。所以，我们在遍历左指针或者右指针之前，要先判断左右两个峰值的大小。

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,  Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

双指针法 复杂度

时间 O(N) 空间 O(1)

思路

我们使用两个指针，一个从左向右遍历，一个从右向左遍历。从左向右遍历时，记录下上次左边的峰值，如果右边一直没有比这个峰值高的，就已经加上这些差值。从右向左遍历时，记录下上次右边的峰值，如果左边一直没有比这个峰值高的，就加上这些差值。难点在于，当两个指针遍历到相邻的峰时，我们要选取较小的那个峰值来计算差值。所以，我们在遍历左指针或者右指针之前，要先判断左右两个峰值的大小。

注意

移动左指针或者右指针时，要先判断left < right

代码

public class Solution {
    public int trap(int[] A) {
        if(A.length < 3) return 0;
        int left = 0;
        int right = A.length - 1;
        int sum = 0;
        // 找到左边的第一个峰值
        while(left < right && A[left] <= A[left+1]) left++;
        // 找到右边的第一个峰值
        while(left < right && A[right] <= A[right-1]) right--;
        while(left < right){
            int leftVal = A[left];
            int rightVal = A[right];
            // 如果左边峰值较小，先计算左边
            if(leftVal < rightVal){
                while(left < right && leftVal >= A[++left]){
                    sum += leftVal - A[left];
                }
            // 如果右边峰值较小，先计算右边
            } else {
                while(left < right && rightVal >= A[--right]){
                    sum += rightVal - A[right];
                }
            }
        }
        return sum;
    }
}

服务器托管私有云 Rain Trapping water 图像识别提取积水深度

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64507.html

[LintCode/LeetCode] Trapping Rain Water [栈和双指针]

摘要：一种是利用去找同一层的两个边，不断累加寄存。双指针法的思想先找到左右两边的第一个峰值作为参照位，然后分别向后向前每一步增加该位与参照位在这一位的差值，加入，直到下一个峰值，再更新为新的参照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

bluesky 2019-08-14 15:19 评论0 收藏0
LeetCode.42 接雨水(Trapping Rain Water)(JS)

摘要：一题目接雨水给定个非负整数表示每个宽度为的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。上面是由数组表示的高度图，在这种情况下，可以接个单位的雨水蓝色部分表示雨水。提交，答案错误。出错的测试用例为。做有意思的题是要付出代价的，代价就是死活做不出来。一、题目接雨水：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。show...

MartinDai 2019-08-23 18:05 评论0 收藏0
Leetcode[42] Trapping Rain Water

摘要：复杂度思路因为蓄水多少取决于比较短的那块板的长度。代码复杂度思路考虑说明时候需要计算蓄水量当的时候，需要计算能储存的水的多少。每次还需要取出一个作为中间值。如果则一直向里面压进去值，不需要直接计算。 Leetcode[42] Trapping Rain Water Given n non-negative integers representing an elevation map ...

jonh_felix 2019-08-14 15:03 评论0 收藏0
leetcode42 Trapping Rain Water

摘要：我先通过堆栈的方法，找到一个封闭区间，该区间可以盛水，该区间的右节点可以作为下一个封闭区间的起点。思路三堆栈的聪明使用在这里，堆栈允许我们渐进的通过横向分割而非之前传统的纵向分割的方式来累加计算盛水量。题目要求 Given n non-negative integers representing an elevation map where the width of each bar...

GitCafe 2019-08-16 10:37 评论0 收藏0
407. Trapping Rain Water II

407. Trapping Rain Water II 题目链接：https://leetcode.com/problems... 参考discussion里的解法：https://discuss.leetcode.com/... 参考博客里的解释：http://www.cnblogs.com/grandy... public class Solution { public int tra...

wenzi 2019-08-16 10:28 评论0 收藏0