[LeetCode] 42. Trapping Rain Water

• Problem: Trapping Rain Water, 利用 histogram 的圖形, 統計可以接的雨水量
• Concept:
• 第 i 個 bin 能接的水量, 被左右高度所決定 (取其小的)
• 而左右的高度, 相當於持續統計的結果 

• leftMaxHeight (i) = max { leftMaxHeight[i-1], height [i-1] }

• 同理, rightMaxHeight 也是, 只是要由右往左統計
• Implementation:

• class Solution {
  public:
      int trap(vector& height) {
          int result = 0;
          if (height.size() < 2) return result;
          vector leftMaxHeight;
          vector rightMaxHeight(height.size(), 0);
          
          leftMaxHeight.push_back(0);
          for (int i = 1; i < height.size(); i++) {                
              leftMaxHeight.push_back(max(leftMaxHeight[i-1], height[i-1]));
          }
          
          for (int i = height.size() - 2; i >= 0; i--) {
              rightMaxHeight[i] = max(rightMaxHeight[i+1], height[i+1]);
          }
          
          for (int i = 0; i < height.size(); i++) {
              int h = min (leftMaxHeight[i], rightMaxHeight[i]) - height[i];
              if (h > 0) result += h;
          }
          return result;
      }
  };