42.接雨水

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 * 104
• 0 <= height[i] <= 105

基本框架

• 对于每一个柱子，计算它脑袋上面能接几个水
• 显然，最左侧、最右侧的柱子不能接水
• 对于中间的柱子：
  • 计算 min = min(左侧最大柱子高度，右侧最大柱子高度)
  • 计算 接水量= min - 自己高度

定义两个数组：

• leftMax：记录对每个位置而言，其左侧最大高度
• rightMax：记录对每个位置而言，其右侧最大高度

求两个数组

动态规划

以求 leftMax 数组为例

• 从左向右遍历数组
• 每一个柱子左侧最大高度，就等于 max(先前那个柱子的左侧最大高度，先前那个柱子的高度)

public int trap(int[] height) {

if (height.length < 3) return 0;

// 由于最后一个柱子接不了水，所以计算一个有效的右侧边界

int lastIndex = height.length - 2;

int[] leftMax = new int[height.length];

int[] rightMax = new int[height.length];

// leftMax

for (int i = 1; i <= lastIndex; i++)

leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);

for (int i = lastIndex; i >= 1; i--)

rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);

// 看看每一根柱子上能接多少水

int water = 0;

for (int i = 1; i <= lastIndex; i++) {

int min = Math.min(leftMax[i], rightMax[i]);

if (min <= height[i]) continue;

// 最小值比当前高度大，才能接住水

water += min - height[i];

}

return water;

}

单调栈