0042. 接雨水

题目地址(42. 接雨水)

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

题目描述

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。示例:输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6

前置知识

空间换时间
双指针
单调栈

公司

阿里
腾讯
百度
字节

双数组

思路

这是一道雨水收集的问题，难度为hard. 如图所示，让我们求下过雨之后最多可以积攒多少的水。

如果采用暴力求解的话，思路应该是枚举每一个位置 i 下雨后的积水量，累加记为答案。

伪代码

for (let i = 0; i < height.length; i++) {  area += (h[i] - height[i]) * 1; // h为下雨之后的水位}

问题转化为求 h 数组，这里 h[i] 其实等于左右两侧柱子的最大值中的较小值，即h[i] = Math.min(左边柱子最大值, 右边柱子最大值)

如上图那么 h 为 [0, 1, 1, 2, 2, 2 ,2, 3, 2, 2, 2, 1]

问题的关键在于求解左边柱子最大值和右边柱子最大值, 我们其实可以用两个数组来表示leftMax,rightMax，以 leftMax 为例，leftMax[i]代表 i 的左侧柱子的最大值，因此我们维护两个数组即可。

关键点解析

建模h[i] = Math.min(左边柱子最大值, 右边柱子最大值)(h 为下雨之后的水位)

代码

代码支持: JS, Python3, C++:

JS Code:

/* * @lc app=leetcode id=42 lang=javascript * * [42] Trapping Rain Water * *//** * @param {number[]} height * @return {number} */var trap = function (height) {  let max = 0;  let volume = 0;  const leftMax = [];  const rightMax = [];  for (let i = 0; i < height.length; i++) {    leftMax[i] = max = Math.max(height[i], max);  }  max = 0;  for (let i = height.length - 1; i >= 0; i--) {    rightMax[i] = max = Math.max(height[i], max);  }  for (let i = 0; i < height.length; i++) {    volume = volume + Math.min(leftMax[i], rightMax[i]) - height[i];  }  return volume;};

Python Code:

class Solution:    def trap(self, heights: List[int]) -> int:        n = len(heights)        l, r = [0] * n, [0] * n        ans = 0        for i in range(1, len(heights)):            l[i] = max(l[i - 1], heights[i - 1])        for i in range(len(heights) - 2, 0, -1):            r[i] = max(r[i + 1], heights[i + 1])        for i in range(len(heights)):            ans += max(0, min(l[i], r[i]) - heights[i])        return ans

C++ Code:

int trap(vector<int>& heights){if(heights == null)return 0;    int ans = 0;    int size = heights.size();    vector<int> left_max(size), right_max(size);    left_max[0] = heights[0];    for (int i = 1; i < size; i++) {        left_max[i] = max(heights[i], left_max[i - 1]);    }    right_max[size - 1] = heights[size - 1];    for (int i = size - 2; i >= 0; i--) {        right_max[i] = max(heights[i], right_max[i + 1]);    }    for (int i = 1; i < size - 1; i++) {        ans += min(left_max[i], right_max[i]) - heights[i];    }    return ans;}

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(N)$

双指针

这种解法为进阶解法，大家根据自己的情况进行掌握。

思路

上面代码比较好理解，但是需要额外的 N 的空间。从上面解法可以看出，我们实际上只关心左右两侧较小的那一个，并不需要两者都计算出来。具体来说：

如果 l[i + 1] < r[i] 那么最终积水的高度由 i 的左侧最大值决定。
如果 l[i + 1] >= r[i] 那么最终积水的高度由 i 的右侧最大值决定。

因此我们不必维护完整的两个数组，而是可以只进行一次遍历，同时维护左侧最大值和右侧最大值，使用常数变量完成即可。这是一个典型的双指针问题，

具体算法：

维护两个指针 left 和 right，分别指向头尾。
初始化左侧和右侧最高的高度都为 0。
比较 height[left] 和 height[right]
- 3.1 如果 height[left] < height[right], 那么瓶颈在于 height[left]，不需要考虑 height[right]
  - 3.1.1 如果 height[left] < left_max，则当前格子积水面积为(left_max - height[left])，否则无法积水，即积水面积为 0。也可将逻辑统一为盛水量为 max(0, left_max - height[left])
  - 3.1.2 左指针右移一位。（其实就是左指针的位置的雨水量已经计算完成了，我们移动到下个位置用同样的方法计算）
- 3.2 否则瓶颈在于 height[right]，不需要考虑 height[left]
  - 3.2.1 如果 height[right] < right_max, 则当前格子积水面积为(right_max - height[left])，否则无法积水，即积水面积为 0。也可将逻辑统一为盛水量为 max(0, right_max - height[right])
  - 3.2.2 右指针右移一位。（其实就是右指针的位置的雨水量已经计算完成了，我们移动到下个位置用同样的方法计算）

代码

代码支持: Python, C++, Go, PHP:

Python Code:

class Solution:    def trap(self, heights: List[int]) -> int:        n = len(heights)        l_max = r_max = 0        l, r = 0, n - 1        ans = 0        while l < r:            if heights[l] < heights[r]:                if heights[l] < l_max:                    ans += l_max - heights[l]                else:                    l_max = heights[l]                l += 1            else:                if heights[r] < r_max:                    ans += r_max - heights[r]                else:                    r_max = heights[r]                r -= 1        return ans

C++ Code:

class Solution {public:    int trap(vector<int>& heights){    int left = 0, right = heights.size() - 1;    int ans = 0;    int left_max = 0, right_max = 0;    while (left < right) {        if (heights[left] < heights[right]) {            heights[left] >= left_max ? (left_max = heights[left]) : ans += (left_max - heights[left]);            ++left;        }        else {            heights[right] >= right_max ? (right_max = heights[right]) : ans += (right_max - heights[right]);            --right;        }    }    return ans;}};

Go Code:

func trap(height []int) int {    if len(height) == 0 {        return 0    }    l, r := 0, len(height)-1    lMax, rMax := height[l], height[r]    ans := 0    for l < r {        if height[l] < height[r] {            if height[l] < lMax {                ans += lMax - height[l]            } else {                lMax = height[l]            }            l++        } else {            if height[r] < rMax {                ans += rMax - height[r]            } else {                rMax = height[r]            }            r--        }    }    return ans}

PHP Code:

class Solution{    /**     * @param Integer[] $height     * @return Integer     */    function trap($height)    {        $n = count($height);        if (!$n) return 0;        $l = 0;        $l_max = $height[$l];        $r = $n - 1;        $r_max = $height[$r];        $ans = 0;        while ($l < $r) {            if ($height[$l] < $height[$r]) {                if ($height[$l] < $l_max) $ans += $l_max - $height[$l];                else $l_max = $height[$l];                $l++;            } else {                if ($height[$r] < $r_max) $ans += $r_max-$height[$r];                else $r_max = $height[$r];                $r--;            }        }        return $ans;    }}