LeetCode42-接雨水

链接：https://leetcode-cn.com/problems/trapping-rain-water/

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

这道题目有好几种解法，比较自然的解法是用动态规划来做。

用两个数组left和right分别记录在任意位置左侧最高的点及右侧最高点，最后将这两个值相减就是可能的储水高度，再和自身高度作差就可以得到结果。每次修改的时候取邻居的值和dp值的max更新dp值就可以。

图源LeetCode

• 时间复杂度：$O(n)$
• 空间复杂的：$O(n)$

  代码

  class Solution {
  public:
      int trap(vector<int>& height) {
          int len = height.size(), sum = 0;
          vector<int> left(height), right(height);
          for(int i = 1; i < len; i++) {
              left[i] = max(height[i - 1], left[i - 1]);
          }
          for(int i = len - 2; i >= 0; i--) {
              right[i] = max(height[i + 1], right[i + 1]);
          }
          for(int i = 0; i < len; i++){
              sum += max(0, min(right[i], left[i]) - height[i]);
          }
          return sum;
      }
  };