美文网首页工作生活
iOS 接雨水算法Swift

iOS 接雨水算法Swift

作者: huxinwen | 来源:发表于2019-07-04 17:19 被阅读0次

题目描述:

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


接雨水题目描述.png

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路:

思路一,时间复杂度由希尔排序决定,最大N*logN,以[90,100,56,10,0,80,30,60]为例:

  1. 降序数组,数组内容为值及对应的原始位置(location,value)[(1,100),(0,90),(5,80),(7,60),(2,56),(6,30),(3,10),(4,0)]
  2. 遍历排序后的数组,根据能够接水的必要条件是两个柱子之间必须有间隙,即不能相邻,拿到可以接水的区间:
  • 100跟90之间没有间隙,找下一个;
  • 100跟80之间有间隙,符合可以接水的必要条件,存储该区间gap =(1,5),并计算该区间可以接水的量:遍历区间(2~4)内的数据container += min(100,80) - arr[i];
  • 继续循环,看是否在gap区间对应(0,6)范围内(其中0和6,如果在,由于已经计算,continue),80不再区间,根据位置关系更新gap为(1,7),计算新增区间(5,7)可以接水的量container += min(100,80) - arr[i];
  • 比较gap区间跟整个数组范围(1,count -2)关系,如果小于等于gap,计算完毕,没有继续c步骤。 思路一.png

    代码如下:

static func trap(_ height: [Int]) -> Int {
        if height.count <= 2 {
            return 0
        }
        let sortHeight = sortArr(arr: height)///降序,拿到值及对应的原始位置 [(原始位置,值)]
        
        var container = 0
        var gap :(Int,Int)?
        
        for k in 0..<sortHeight.count-1 {
            let firstL = sortHeight[k]
            guard let gugap = gap else {
                var i = k+1
                
                while (gap ?? nil) == nil && i < sortHeight.count{///从最大值(如果不是最大值开始,可能漏算)开始,拿到第一段可以接水的区间。
                    let secondL = sortHeight[I]
                    if abs(firstL.0 - secondL.0) > 1 { ///可以接水的必要条件是,两个柱子之间有间隙
                        let start = min(secondL.0, firstL.0)
                        let end = max(secondL.0, firstL.0)
                        gap = (start,end)///保存区间
                        for g in start + 1...end-1 {///计算此区间可以接水的量
                            container += secondL.1 - height[g] < 0 ? 0:secondL.1 - height[g]///虽然中间有间隔,但是不能保证能接水,去掉不能接水,即中间的柱子不是最小
                            
                        }
                        if start <= 1 && end >= sortHeight.count - 2{
                            return container
                        }
                    }
                    i += 1
                }
                continue
            }
            if firstL.0 <= gugap.1 + 1 && firstL.0 >= gugap.0 - 1  {///在已经结算的区间内,continue
                continue
            }else{///不再已经结算的区间,根据位置关系,更新结算区间
                var start = 0
                var end  = 0
                if firstL.0 > gugap.1 {///在右边
                    start = gugap.1
                    end = firstL.0
                    gap = (gugap.0,end)
                }else{///在左边
                    start = firstL.0
                    end = gugap.0
                    gap = (start,gugap.1)
                }
                for g in start + 1...end-1 {///计算新增区间可以接水的量,同样可能会有不能接水的可能,剔除
                    container += firstL.1 - height[g] < 0 ? 0:firstL.1 - height[g]
                    
                }
                if start <= 1 && end >= sortHeight.count - 2{
                    return container
                }
            }
        }
        return container
    }
    static func sortArr(arr:[Int]) -> [(Int,Int)] {///希尔排序
        let count = arr.count
        var locValueTump :[(Int,Int)] = []
        for i in 0..<count {
            locValueTump.append((i,arr[i]))///记录位置及对应的值
        }
        
        var gap = count/2
        while gap > 0 {
            for i in gap..<count{
                var j = I
                let temp = locValueTump[j]
                if locValueTump[j].1 > locValueTump[j-gap].1 {
                    while j-gap>=0 && temp.1 > locValueTump[j-gap].1 {
                        locValueTump[j] = locValueTump[j-gap]
                        j -= gap
                    }
                    locValueTump[j] = temp
                }
            }
            gap /= 2
        }
        
        return locValueTump
    }

思路二,比较暴力时间复杂度O(n^2):

  1. 从数组的第二个元素开始到倒数第二个元素遍历,,向左向右分别取到最大值max_left,max_right;
  2. 计算接水量 container += min(max_left,max_right) - height[I]。 思路二.png
static func trap(_ height: [Int]) -> Int {
        if height.count <= 2 {
            return 0
        }
        var ans = 0;
        let size = height.count;
        for i in 0..<size - 1 {//向左寻找最大
            var max_left = 0, max_right = 0;
            for j in 0...i { //Search the left part for max bar size
                max_left = max(max_left, height[j]);
            }
            for j in i..<size { //向右边查找最大值
                max_right = max(max_right, height[j]);
            }
            ans += min(max_left, max_right) - height[i];
        }
        return ans;
}

接雨水

相关文章

  • iOS 接雨水算法Swift

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

  • Swift刷算法:接雨水

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

  • 算法:接雨水

    问题 Given n non-negative integers representing an elevatio...

  • Java算法(3):接雨水

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

  • 接雨水的算法题

    前几天看到一个算法题就写了一下如下: 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,...

  • [iOS开发--Swift 如何完成工程中Swift和OC的混编

    [iOS开发--Swift 如何完成工程中Swift和OC的混编桥接(Cocoapods同样适用)] 最快捷的方式...

  • IOS 算法合集

    这里用来总结记录所有算法(大部分Swift) 中级篇IOS 算法(中级篇) ----- 三数之和求解问题[http...

  • 接雨水

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

  • 接雨水

    题目来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/trap...

  • 接雨水

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

网友评论

    本文标题:iOS 接雨水算法Swift

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