Problem Description

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. Thanks Marcos for contributing this image!

Analyze

1、找出最高的柱子，以此柱為中線將數(shù)組分為兩半
2、處理左邊一半：從左往右計算柱子高度極大值與當(dāng)前柱子高度差
3、處理右邊一半：從右往左同2

Code

class Solution {
    func trap(heights: [Int]) -> Int {
        let n = heights.count
        var water = 0
        var max: Int = 0
       
        for (i, value) in heights.enumerate() {
            if value > heights[max] {
                max = i //找出最高的柱子 將數(shù)組分為兩半
            }
        }
        
        var peak = 0 // 謹(jǐn)記數(shù)據(jù)越界問題, 不能取heights[0]
         for value in heights[0..<max] {
            if value < peak {
                water += peak - value
            }
            else if value > peak {
                peak = value
            }
        }
        
        var top = 0
        for value in heights[max..<n].reverse() {
            if value < top {
                water += top - value
            }
            else if value > top {
                top = value
            }
        }
        
        return water
    }
}