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:

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 volumn = 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++) {
        volumn = volumn +  Math.min(leftMax[i], rightMax[i]) - height[i]
    }

    return volumn;
};

Python Code:

class Solution:
    def trap(self, height: List[int]) -> int:
        maxLeft, maxRight, volum = 0, 0, 0
        maxLeftStack, maxRightStack = [], []
        for h in height:
            if h > maxLeft:
                maxLeftStack.append(h)
                maxLeft = h
            else:
                maxLeftStack.append(maxLeft)
        for h in height[::-1]:
            if h > maxRight:
                maxRightStack.append(h)
                maxRight = h
            else:
                maxRightStack.append(maxRight)
        maxRightStack = maxRightStack[::-1]
        for i in range(1, len(height) - 1):
            minSide = min(maxLeftStack[i], maxRightStack[i])
            volum += minSide - height[i]
        return volum