美文网首页
42. 接雨水

42. 接雨水

作者: 邦_ | 来源:发表于2022-07-26 10:51 被阅读0次

每个柱子上的雨水 = min(柱子左边的最大值,柱子右边的最大值) - height[i]


func trap(_ height: [Int]) -> Int {

        var water = 0
        let len = height.count
        var leftValue = height[0]
        var rightArray = Array.init(repeating: 0, count: len)
        rightArray[len - 1] = height[len - 1]
        for i in (0..<len - 1).reversed() {
            rightArray[i] = max(rightArray[i + 1], height[i])
        }
        for i in 0..<len {
            leftValue = max(leftValue, height[i])
            water += min(leftValue,rightArray[i]) - height[i]
        }
       

        return water
    
    }


最后这种思路比较难想


func trap(_ height: [Int]) -> Int {

        let len = height.count
        var water = 0 ,lowerMax = 0 ,l = 0 ,r = len - 1

        while l < r {
            var lower = 0
            if height[l] <= height[r]  {
                lower = height[l]
                l += 1
            }else {
                lower = height[r]
                r -= 1
            }
            lowerMax = max(lowerMax, lower)
            water += lowerMax - lower

        }
       

        return water
    
    }




相关文章

  • 42. 接雨水

  • 42. 接雨水

    ···class Solution {public int trap(int[] height) {int sum...

  • 42. 接雨水

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 ...

  • 42. 接雨水

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 ...

  • 42.接雨水

    题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。输入:...

  • 42. 接雨水

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。柱状图上面是由数...

  • 42. 接雨水

    题目描述 给定n个非负整数表示宽度为1的柱子高度,按此排序下雨后能接多少水。 示例: 解题思路 每个柱子可接的水量...

  • 42. 接雨水

    题目给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例:输入...

  • 42. 接雨水

  • 42. 接雨水

    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 ...

网友评论

      本文标题:42. 接雨水

      本文链接:https://www.haomeiwen.com/subject/neggirtx.html