42. 接雨水

难度：困难

题目

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

示例 1：

输入：height = [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 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 0 <= n <= 3 * 10^4
• 0 <= height[i] <= 10^5

Reference

注：本题与面试题 17.21. 直方图的水量相同。

题解

1. 分治算法，水的高度不会高于最高的柱子，因此可以在最高的柱子\(A\)与次高的柱子\(B\)两处进行分割，分别求解三段容纳的水量。

   \(A, B\)之间必然可以容纳水，水的量等于各个柱子到次高柱子的高度之和。其他区间需要递归进行求解。需要注意分割时分割点要同时包含在左右两侧，否则无法容纳水。

   当柱子数量小于3时，无法容纳任何水。

   #define MAX(x, y) (x > y ? x : y)
   #define MIN(x, y) (x < y ? x : y)
   
   int trap(int* height, int heightSize){
       int *maxLeft = (int *)malloc(sizeof(int) * heightSize),
           *maxRight = (int *)malloc(sizeof(int) * heightSize),
           i = 0, ret = 0;
       if (heightSize == 0)
           return 0;
       maxLeft[0] = height[0];
       maxRight[heightSize - 1] = height[heightSize - 1];
       for (i = 1; i < heightSize; i++)
       {
           maxLeft[i] = MAX(maxLeft[i - 1], height[i - 1]);
           maxRight[heightSize - i - 1] = MAX(maxRight[heightSize - i], height[heightSize - i]);
       }
       for (i = 0; i < heightSize; i++)
           ret += MAX(0, MIN(maxLeft[i], maxRight[i]) - height[i]);
       return ret;
   }
   

   总的时间复杂度为\(\mathcal O(N)\)。

2. 直接思路，对于每个柱子，其容纳水后的高度（柱子高度减去水高度）等于该柱子左侧最高柱子的高度与右侧最高柱子的高度的最小值。因此，对于每个柱子，可以统计在其左侧最高柱子的高度与在其右侧最高柱子的高度，存储在两个数组中。

   结果为每个柱子容纳水后的高度与柱子高度之差的求和。

   #define MAX(x, y) (x > y ? x : y)
   #define MIN(x, y) (x < y ? x : y)
   
   int trap(int* height, int heightSize){
       int *maxLeft = (int *)malloc(sizeof(int) * heightSize),
           *maxRight = (int *)malloc(sizeof(int) * heightSize),
           i = 0, ret = 0;
       if (heightSize == 0)
           return 0;
       maxLeft[0] = height[0];
       maxRight[heightSize - 1] = height[heightSize - 1];
       for (i = 1; i < heightSize; i++)
       {
           maxLeft[i] = MAX(maxLeft[i - 1], height[i - 1]);
           maxRight[heightSize - i - 1] = MAX(maxRight[heightSize - i], height[heightSize - i]);
       }
       for (i = 0; i < heightSize; i++)
           ret += MAX(0, MIN(maxLeft[i], maxRight[i]) - height[i]);
       return ret;
   }
   

评论