42. Trapping Rain Water 收集雨水

[GH1995]

42. Trapping Rain Water

Difficulty: Hard

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.

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!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Solution

Language: C++

class Solution {
public:
    int trap(vector<int> &height) {
      int n = height.size();
​
      vector<int> maxLeft(n, 0);
      vector<int> maxRight(n, 0);
​
      for (int i = 1; i < n; ++i) // 0 号左边最高的元素(不包括当前值)是0
        maxLeft[i] = max(maxLeft[i - 1], height[i - 1]);
​
      for (int i = n - 2; i >= 0; --i) // n-1 号元素右边最高的元素（不包括当前值）为0
        maxRight[i] = max(maxRight[i + 1], height[i + 1]);
​
      int sum = 0;
      for (int i = 0; i < n; ++i) {
        auto temp = min(maxLeft[i], maxRight[i]) - height[i];
        if (temp > 0)
          sum += temp;
      }
​
      return sum;
    }
};

[GH1995]

对于每根柱子，找到其左右两边最高的柱子，该柱子能容纳的面积就是min(maxLeft[i], maxRight[i]) - height[i]。

---

  for (int i = 1; i < n; ++i) // 0 号左边柱子的元素(不包括当前值)是0
    maxLeft[i] = max(maxLeft[i - 1], height[i - 1]);

  for (int i = n - 2; i >= 0; --i) // n-1 号元素右边最高的柱子（不包括当前值）为0
    maxRight[i] = max(maxRight[i + 1], height[i + 1]);