区块链技术博客
www.b2bchain.cn

LeetCode题解42.trapping-rain-water程序员分享

本文介绍了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      

题目地址 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…

题目地址 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). …

题目地址 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 …

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

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

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » LeetCode题解42.trapping-rain-water程序员分享
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们