iOS 接雨水算法Swift

题目描述：

给定 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;
}

接雨水