Problem

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.

Water

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.

Solution

用兩個(gè)數(shù)組愈污，維護(hù)從左邊到當(dāng)前的元素最大高度，另外一個(gè)是從右邊到當(dāng)前元素的最大高度。當(dāng)前元素的積水高度就取決于左右兩邊的較小值 - 當(dāng)前元素高度。

Swift

class Solution {
  func trap(height: [Int]) -> Int {
    if height.count == 0 {
      return 0
    }
    var leftMax: [Int] = []
    var rightMax: [Int] = []
    var maxH = -1
    for h in height {
      leftMax.append(maxH)
      maxH = max(maxH, h)
    }
    maxH = -1
    for h in height.reverse() {
      rightMax.insert(maxH, atIndex: 0)
      maxH = max(maxH, h)
    }
    
    var ret : Int = 0
    for i in 0..<leftMax.count {
      let h = min(leftMax[i], rightMax[i])
      let water = max(0, h - height[i])
      ret += water
    }
    
    return ret
  }
}

另一種思路：Time: O(n), Space: O(1)
維護(hù)左右兩個(gè)指針，然后朝里推進(jìn)丘侠。于此同時(shí)，維護(hù)左右兩邊的最大高度。如果左邊的較小缺亮，左邊指針向右推進(jìn)，然后根據(jù)左右兩邊最小的高度確定當(dāng)前格子可以存多少水桥言。這里的關(guān)鍵是萌踱，將左右兩邊更小的那個(gè)指針向里推進(jìn)，有點(diǎn)像非遞減序列地去填水号阿。

Swift

class Solution {
  func trap(height: [Int]) -> Int {
    if height.count == 0 {
      return 0
    }
    var i = 0
    var j = height.count - 1
    var ret = 0
    var leftHeight = height[0]
    var rightHeight = height[j]
    while i < j {
      let minHeight = min(leftHeight, rightHeight)
      if (leftHeight < rightHeight) {
        i += 1
        let water = max(minHeight - height[i], 0)
        ret += water
        leftHeight = max(leftHeight, height[i])
      } else {
        j -= 1
        let water = max(minHeight - height[j], 0)
        ret += water
        rightHeight = max(rightHeight, height[i])
      }
    }
    
    return ret
  }
}

C++

class Solution {
public:
    /**
     * @param heights: a vector of integers
     * @return: a integer
     */
    int trapRainWater(vector<int> &heights) {
        if (heights.size() == 0) {
            return 0;
        }
        int i = 0;
        int j = heights.size() - 1;
        int leftHeight = heights[i];
        int rightHeight = heights[j];
        int ret = 0;
        while (i < j) {
            int minHeight = min(leftHeight, rightHeight);
            if (leftHeight < rightHeight) {
                i++;
                int water = max(minHeight - heights[i], 0);
                ret += water;
                leftHeight = max(leftHeight, heights[i]);
            } else {
                j--;
                int water = max(minHeight - heights[j], 0);
                ret += water;
                rightHeight = max(rightHeight, heights[j]);
            }
        }
        return ret;
    }
};