42.trapping-rain-water.md

题目地址

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

题目描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.


The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

前置知识

• 空间换时间
• 双指针
• 单调栈

公司

• 阿里
• 腾讯
• 百度
• 字节

双数组

思路

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

如果采用暴力求解的话，思路应该是 height 数组依次求和，然后相加。

伪代码:

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 为下雨之后的水位)

代码

代码支持 JavaScript，Python3，C++:

JavaScript 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 + 1), [0] * (n + 1)
        ans = 0
        for i in range(1, len(heights) + 1):
            l[i] = max(l[i - 1], heights[i - 1])
        for i in range(len(heights) - 1, 0, -1):
            r[i] = max(r[i + 1], heights[i])
        for i in range(len(heights)):
            ans += max(0, min(l[i + 1], 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 的右侧最大值决定。

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

具体算法：

1. 维护两个指针 left 和 right，分别指向头尾。

2. 初始化左侧和右侧最高的高度都为 0。

3. 比较 height[left] 和 height[right]

   • 3.1 如果 height[left] < height[right]

     • 3.1.1 如果 height[left] >= left_max， 则当前格子积水面积为(left_max - height[left])
     • 3.1.2 否则无法积水，即积水面积为 0

   • 3.2 左指针右移一位

   • 3.3 如果 height[left] >= height[right]

     • 3.3.1 如果 height[right] >= right_max， 则当前格子积水面积为(right_max - height[right])
     • 3.3.2 否则无法积水，即积水面积为 0

   • 3.4 右指针左移一位

代码

代码支持 Python3，C++:

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

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;
}

};

复杂度分析

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

相关题目

• 84.largest-rectangle-in-histogram

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 30K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。