资讯专栏INFORMATION COLUMN

Trapping water

hlcc / 1509人阅读

摘要:思路对于每一个来说,能装水的容量取决于左右两侧的最大值。一个的最终高度容器高度由左右边界中较小的一个决定。最终求和得到总蓄水量。对撞指针问题,根据左右两边中较矮的柱子确定当前的柱子的最终高度。两边最大灌水量分别等于分别当前最大高度。

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.

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

思路
对于每一个bar来说,能装水的容量取决于左右两侧bar的最大值。一个bar的最终高度 = MIN (Max_left_height, Max_right_height). 容器高度由左右边界中较小的一个决定。
brute force 思路: 扫描两次,一次从左向右,记录对于每一个bar来说其左侧的bar的最大高度left[i],一次从右向左,记录每一个bar右侧bar的最大高度right[i]。第三次扫描,则对于每一个bar,计算(1)左侧最大height和当前bar的height的差值(left[i] - heights[i]) (2)右侧最大height和当前bar的height的差值(right[i] - heights[i]),取(1),(2)中结果小的那个作为当前bar的蓄水量。最终求和得到总蓄水量。

Two Pointers
对撞指针问题, 根据左右两边中较矮的柱子确定当前的柱子的最终高度。 两边最大灌水量分别等于 分别 += 当前最大高度 - heights[i]。

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: a integer
     */
    public int trapRainWater(int[] heights) {
        // write your code here
        if (heights == null || heights.length == 0){
            return 0;
        }
        int left = 0, right = heights.length-1;
        if (left >= right){
            return 0;
        }
        //对撞型指针问题, 左右两边更低的那根柱子决定了能灌水多少--> 比较左右两根柱子, 根据两者高低靠近, 过程中更新左边和右边的最大值(最大高度)
        //两边最大灌水量分别 += 当前最大高度 - heights[i] 
        //两指针未相遇时, leftH(左边最大高度) - heights[left]; right
        int leftHeight = heights[0];
        int rightHeight = heights[heights.length -1];
        int res = 0;
        
        while (left < right){
            if (heights[left] < heights[right]){
                left++;
                if (heights[left] < leftHeight){
                    res += leftHeight - heights[left];
                }
                else{
                    leftHeight = heights[left];
                }
            }else{
                right--;
                if (heights[right] < rightHeight){
                    res += rightHeight - heights[right];
                }else{
                    rightHeight = heights[right];
                }
            }
        }
        
        return res;
    }
}

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

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

相关文章

  • 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 评论0 收藏0
  • [Leetcode] Trapping Rain Water 积水问题

    摘要:从右向左遍历时,记录下上次右边的峰值,如果左边一直没有比这个峰值高的,就加上这些差值。难点在于,当两个指针遍历到相邻的峰时,我们要选取较小的那个峰值来计算差值。所以,我们在遍历左指针或者右指针之前,要先判断左右两个峰值的大小。 Trapping Rain Water Given n non-negative integers representing an elevation map ...

    caohaoyu 评论0 收藏0
  • Leetcode[42] Trapping Rain Water

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

    jonh_felix 评论0 收藏0
  • 42. Trapping Rain Water

    摘要:题目解答左边比右边小或者大都可以盛水,所以我们不能直接确定右边是否会有一个柱子比较大,能盛所有现在积攒的水。那么我们就找到中间最大的那个柱子,把它分成左右两边,那么不管从左边还是右边都能保证最后可以有最高的柱子在,之前盛的水都是有效的 题目:Given n non-negative integers representing an elevation map where the wid...

    seanlook 评论0 收藏0
  • [LintCode/LeetCode] Trapping Rain Water [栈和双指针]

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

    bluesky 评论0 收藏0

发表评论

0条评论

hlcc

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<