给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
leetcode_42.接雨水 - 图1

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

c plus

  1. 按列求，是求本列上面能放多少水，这个和左边最大高度，右边最大高度的较小值有关。即本列存水=较小值-本列的值

  2. 注意 int max_left = 0; int max_right = 0;定义在for循环里面，每一列都要求左最大和右最大。粗心定义在外面则会出错。

    1. //直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值
    2. class Solution {
    3. public:
    4.  int trap(vector<int>& height) {
    5.      int length = height.size();
    6.      if (length <= 1) return 0;
    7.      int sum = 0;
    8.      for (int i = 1; i < length- 1; i++) {
    9.          int max_left = 0;
    10.          int max_right = 0;
    11.          for (int j = i - 1; j >= 0; j--) { //求左边最大
    12.              if (height[j] > max_left) {
    13.                  max_left = height[j];
    14.              }
    15.          }
    16.          for (int j = i + 1; j < length; j++) { //求右边最大
    17.              if (height[j] > max_right) {
    18.                  max_right = height[j];
    19.              }
    20.          }
    21.          int min_height = min(max_left, max_right);
    22.          if (min_height > height[i]) {
    23.              sum += min_height - height[i];
    24.          }
    26.      }
    27.      return sum;
    28.  }
    29. };
  • 动态规划
  1. 优化上面解法找左边最大高度和右边最大高度的过程。
  2. 先把每列的左最大和右最大找出来，存到数组里面去:
  3. 当前列的左边界最大值，肯定是前一列的左边界最大值和前一列的值中的较大者。

maxLeft[i] 存储中间态，以中间态去推导其他的中间态，也就是DP 方程
也就是当前列的左边界最大值，肯定是前一列的左边界最大值和前一列的值中的较大者。
maxLeft[i] = max(maxLeft[i - 1], height[i - 1]);

  1. class Solution {
  2.     public:
  3.     int trap(vector<int>& height) {
  4.         int sum = 0;
  5.         int len = height.size();
  6.         vector<int>maxLeft(len, 0);
  7.         vector<int>maxRight(len, 0);
  8.         for (int i = 1; i < len - 1; i++) {                 //最后一列是存不到水的，所以不用求
  9.             maxLeft[i] = max(maxLeft[i - 1], height[i - 1]);//左边最大从左边开始找
  10.         }
  11.         for (int i = len - 2; i >= 0; i--) {
  12.             maxRight[i] = max(maxRight[i + 1], height[i + 1]);//右边最大从右边开始找
  13.         }
  14.         for (int i = 1; i < len - 1; i++) {
  15.             int m = min(maxLeft[i], maxRight[i]);
  16.             if (m > height[i]) {
  17.                 sum += (m - height[i]);
  18.             }
  19.         }
  20.         return sum;
  21.     }
  22. };
  1. func trap(height []int) int {
  2.     length := len(height)
  3.     if length <= 2 {
  4.         return 0
  5.     }
  6.     sum := 0
  7.     leftMax := make([]int, length)
  8.     rightMax := make([]int, length)
  9.     for i := 1; i < length - 1; i++ {
  10.         leftMax[i] = max(leftMax[i - 1], height[i - 1])
  11.     }
  12.     for i := length - 2; i >= 0; i-- {
  13.         rightMax[i] = max(rightMax[i + 1], height[i + 1])
  14.     } 
  15.     for i := 1; i < length - 1; i++ {
  16.         minHeight := min(leftMax[i], rightMax[i])
  17.         if minHeight > height[i] {
  18.             sum += minHeight - height[i]
  19.         }
  20.     }
  21.     return sum
  22. }
  23. func min(a int, b int) int {
  24.     if a <= b {
  25.         return a
  26.     }
  27.     return b
  28. }
  29. func max(a int, b int) int {
  30.     if a <= b {
  31.         return b
  32.     }
  33.     return a
  34. }