12、Trapping Rain Water

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、找出最高的柱子，以此柱为中线将数组分为两半
2、处理左边一半：从左往右计算柱子高度极大值与当前柱子高度差
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 //找出最高的柱子 将数组分为两半
            }
        }
        
        var peak = 0 // 谨记数据越界问题, 不能取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
    }
}