LeetCode题解42.trapping-rain-water

题目地址

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!


LeetCode题解42.trapping-rain-water

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为 [1, 1, 2, 2, ,2 ,2, ,3, 2, 2, 2, 1]

问题转化为求h,那么h[i]又等于左右两侧柱子的最大值中的较小值,即
h[i] = Math.min(左边柱子最大值, 右边柱子最大值)

问题的关键在于求解左边柱子最大值右边柱子最大值,
我们其实可以用两个数组来表示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      
LeetCode题解365.water-and-jug-problem

题目地址 https://leetcode.com/problems/water-and-jug-problem/description/ 题目描述 You are given two jugs with capacities x and y litres. There is an infinite amount of water supply availa…

LeetCode题解11.container-with-most-water

题目地址 https://leetcode.com/problems/container-with-most-water/description/ 题目描述 Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). …

LeetCode题解1168.optimize-water-distribution-in-a-village-cn

题目地址 https://leetcode.com/problems/optimize-water-distribution-in-a-village/ 题目描述 There are n houses in a village. We want to supply water for all the houses by building wells and …

LeetCode题解计算机为什么是基于二进制的?

可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制

LeetCode题解深度优先遍历和回溯的关系?

深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。