给定n个表示海拔图的非负整数，其中每根钢筋的
宽度为1，计算它能够浇多少水雨后的陷阱
。
上面的海拔图由array
[0,1,0,2,1,0,1,3,2,1,2,1]表示。在这种情况下，将捕获6单位的雨水（蓝色部分）。感谢Marcos贡献了这张照片！
示例：
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
我的解决方案
/**
* @param {number[]} height
* @return {number}
*/
function trap(height) {
let res = 0;
const LEN = height.length;
for (let i = 1; i < LEN - 1; i++) {
let maxLeft = 0, maxRight = 0;
for (let j = i; j >= 0; j--) {
maxLeft = Math.max(maxLeft, height[j]);
}
for (let j = i; j < LEN; j++) {
maxRight = Math.max(maxRight, height[j]);
}
res += Math.min(maxLeft, maxRight) - height[i];
}
return res;
};
#1 楼
您编写了非常清晰易懂的代码：变量名表示目的
您使用
const和let而不是旧的var 封装函数中所有有趣的代码，这使得复制和重用代码变得很容易
您选择在位置上使用尽可能少的临时内存（4个局部变量，没有数组或其他对象）需要更多执行时间的成本，\ $ \ mathcal O \ left（\ text {len}（\ textit {height}）^ 2 \ right）\ $。如果以后需要它，可以通过为所有
maxRight计算一次i并将其存储在一个您可以通过计算
for来优化内部maxLeft循环，因为只能通过查看先前的maxLeft和当前height[i]来计算它：：function trap(height) {
const len = height.length;
let result = 0;
if (len === 0)
return 0;
let maxLeft = height[0];
for (let i = 1; i < len - 1; i++) {
maxLeft = Math.max(maxLeft, height[i]);
...
}
...
}
如果
maxRight等于height[i - 1]，则只需要重新计算即可。因为如果不是，则最大高度不能更改。这两个优化破坏了当前代码的美观对称性。因此，您可能会或可能不想应用它们。在任何情况下，您都应该知道它们存在。常数是随时间变化的值。此
len变量取决于LEN参数，因此在多次调用len函数之间可能会有所不同。评论
\ $ \ begingroup \ $
谢谢。我知道这不是最佳选择，因为代码会在多个时间相同的值上进行迭代。待会我会改善。
\ $ \ endgroup \ $
–thadeuszlay
19年6月2日在17:13
\ $ \ begingroup \ $
为什么需要将maxRight存储在数组中？不只是一个（标量）值吗？
\ $ \ endgroup \ $
–所罗门·乌科（Solomon Ucko）
19年6月3日在1:54
\ $ \ begingroup \ $
@Solomon，以防您想加快算法的速度。第一步，您可以在开始时重新计算一次maxRight，然后在height [i] == maxRight之后再计算一次。并且，如果那还不够快，您可以在高度上进行一次迭代，并记住maxRight实际更改的所有索引。这需要时间O（n）和空间O（n）。
\ $ \ endgroup \ $
–罗兰·伊利格（Roland Illig）
19年6月3日在6:01
\ $ \ begingroup \ $
@Solomon的关键点在于无法通过按正常顺序迭代数组来计算maxRight，因此迭代需要向后进行。
\ $ \ endgroup \ $
–罗兰·伊利格（Roland Illig）
19年6月3日在6:02
\ $ \ begingroup \ $
@RolandIllig我对您的解释有些困惑，但我想我理解您的意思：新元素从相反的方向添加到maxLeft和maxRight中，因此只能使用其中一个（在本例中为maxLeft）与主循环的方向相同。
\ $ \ endgroup \ $
–所罗门·乌科（Solomon Ucko）
19年6月3日在10:42
#2 楼
这纯粹是样式，但是我会在循环周围添加一些间距。
我也不是同一行上有多个声明的支持者，因此我将
maxLeft和maxRight声明分开。最后，该参数可以说是
heights。 height建议它是一个代表高度的数字，而实际上是多个高度值。function trap(heights) {
let res = 0;
const LEN = heights.length;
for (let i = 1; i < LEN - 1; i++) {
let maxLeft = 0
let maxRight = 0;
for (let j = i; j >= 0; j--) {
maxLeft = Math.max(maxLeft, heights[j]);
}
for (let j = i; j < LEN; j++) {
maxRight = Math.max(maxRight, heights[j]);
}
res += Math.min(maxLeft, maxRight) - heights[i];
}
return res;
};
空格使代码有点堆积，但是我总是发现，如果代码没有全部压缩在一起，则更易于阅读。
评论
\ $ \ begingroup \ $
我链接到的图像很大（30,000x20,000像素；〜75mb），因此Drive无法正确预览。
\ $ \ endgroup \ $
–致癌物质
19年6月2日在18:25
\ $ \ begingroup \ $
Mod note：评论仅用于澄清和讨论其所附的帖子。非常欢迎您在Code Review Chat中社交：)
\ $ \ endgroup \ $
–Vogel612♦
19年5月5日在9:42
#3 楼
审查复杂性到目前为止，只有一个答案解决了复杂性问题，这是对您的解决方案的重大改进。由于现有的答案已解决了代码样式，因此我会坚持使用复杂性，因为没有一个较复杂的解决方案。
双向寻找！查找下一个峰，从而计算捕获的体积。您对每个海拔高度执行此操作，因此会得到\ $ O（n ^ 2）\ $和\ $ O（1）\ $存储的复杂度。
一个答案的建议是存储最大值快速参考，这意味着您需要将存储增加到\ $ O（n）\ $才能获得\ $ O（n）\ $复杂性，这是一个更好的方法。
后退。
要解决\ $ O（1）\ $存储空间和\ $ O（n）\ $复杂度，请使用两次跟踪通过的方法，用于跟踪您已经越过的峰高（向后看，而不是双向看）。
一种从左向右检查所有高程，从右向左检查仅用于高程的方法在第一遍中发现的最高峰。
最多最多可以越过每个海拔两次，最好的情况是，如果最右边的最高海拔是最高的，则只需要越过每个海拔一次。通过将迭代次数减少到平均\ $ n * 1.5 \ $而不是\ $ n * 2 \ $
[ 1]注意性能并不意味着复杂性
示例
\ $ O（1）\ $存储空间，\ $ O（n）\ $复杂度解决方案
我检查了其对您函数的正确性，（旨在获得大量测试，到目前为止，两个函数对随机数据进行了十亿次测试）
function floodVolume(elevations) {
var peakIdx, i = 0, peak = 0, volume = 0, total = 0;
const depth = (i, elevation = elevations[i]) => {
if (elevation >= peak) {
peak = elevation;
peakIdx = i;
total += volume;
volume = 0;
} else { volume += peak - elevation }
}
while (i < elevations.length) { depth(i++) }
const MAX_IDX = peakIdx;
volume = peak = 0;
while (i-- >= MAX_IDX) { depth(i) }
return total;
}
评论
\ $ \ begingroup \ $
Mod note：评论仅用于澄清和讨论其所附的帖子。非常欢迎您在Code Review Chat中社交：)
\ $ \ endgroup \ $
–Vogel612♦
19年5月5日在9:43
#4 楼
您可能会喜欢以下更实用的方法：function trappedWater(heights) {
const maxSoFar = arr => arr.reduce((m, x) => m.concat(Math.max(...m, x)), [])
const leftWall = arr => [0, ...maxSoFar(arr).slice(0, -1)]
const l = leftWall(heights)
const r = leftWall(heights.reverse()).reverse()
return heights.reduce((m, h, i) => m + Math.max(0, Math.min(l[i], r[i]) - h), 0)
}
在线尝试！
主要区别在于我们首先计算左“墙”使用相同的
leftWall函数（本身使用“扫描和”实用程序函数）为每个索引设置“高度”和右侧的“墙”高度，并注意可以通过将rightWall应用于两个输入和输出。任意索引处的水量为左右壁高的最小值减去该点的高度；如果该数字为负，则为零。然后我们将所有这些加起来。
#5 楼
进一步发挥功能，分解映射功能，加一点咖喱味。 // Curried initialization of the current max value
const maxSoFar = max => n => max = Math.max(max, n)
// The max previous value; like max current but shifted to the right with a zero first
const maxPrevious = arr => [0, ...(arr.map(maxSoFar(0)))].slice(0, -1)
// Note the [...arr] - .reverse() changes the original. Not very functional
const maxFollowing = arr => maxPrevious([...arr].reverse()).reverse()
// Function to get mapping function subtracting two arrays
const subtract = otherArr => (n, index) => n - otherArr[index]
// Like above, but taking the minimum value
// Non-currying to make the main function more readable
const min = (arr, other) => arr.map((n, index) => Math.min(n, other[index]))
const trappedWater = heights => min(maxPrevious(heights), maxFollowing(heights))
.map(subtract(heights))
.filter(n => n > 0) // Positive only
.reduce((a,b) => a + b, 0) // Sum the array
console.log(trappedWater([0,1,0,2,1,0,1,3,2,1,2,1]))
console.log(trappedWater([0,1,1,0]))
评论
\ $ \ begingroup \ $
是的！功能主义！
\ $ \ endgroup \ $
– Stefano
19年6月3日在15:10
\ $ \ begingroup \ $
我必须开始练习FP和curring。截至目前，该代码对我来说已经太挤满了
\ $ \ endgroup \ $
–卡尔斯·阿尔科利亚
19年4月4日在20:17
\ $ \ begingroup \ $
我熟悉FP，但这很难遵循。而且，它速度较慢，只要您可以编写得更简洁，可读性更好，就可以接受。但这不是事实。此外，您还忘了在reduce中初始化累加器。还有一些评论是多余的，例如最后两个。
\ $ \ endgroup \ $
–thadeuszlay
19年4月4日在21:27
\ $ \ begingroup \ $
如果在空数组（没有初始值）上调用reduce函数会发生什么？
\ $ \ endgroup \ $
–thadeuszlay
19 Jun 5 '19在7:32
\ $ \ begingroup \ $
是的。我认为最好总是提供一个初始值
\ $ \ endgroup \ $
–thadeuszlay
19年5月5日在7:42
#6 楼
我偶然发现了你的问题（我通常只访问stackoverflow），最后决定注册一个帐户。这个主意
我看到@ Blindman67答案（我不能注释，因为我没有足够的声誉），我想知道是否可以将迭代次数从n * 1.5减少到n。因此，我提出了这个想法。创建两个不同的指针，而不是一路求右，然后再返回。
指针
i从左到右，指针j从右到左。这个想法是获取第一个和最后一个块，并找出哪个更高。然后，使用最低的墙作为墙壁。如果是maxL < maxR，我们将向上移动，然后将height[i]与maxL进行比较，因为我们可以肯定地知道在右侧某处会保留水的壁。另一方面，如果maxR < maxL，我们做相反的事情。每次将i与maxL进行比较，将j与maxR进行比较，则当i=j表示对数组中的每个点进行求值时。示例代码
我相信解决方案仍然是O（n）的复杂性和O（i）的存储，但是我对此领域的知识很少，所以如果有人可以确认我将不胜感激。 />
评论
\ $ \ begingroup \ $
我喜欢这个主意
\ $ \ endgroup \ $
–thadeuszlay
19年5月5日在4:42
\ $ \ begingroup \ $
欢迎使用CR ... +1是，您具有复杂性和正确的存储功能，性能平均提高了33％。我可以建议删除moveUp并声明是否（maxL
– Blindman67
19年6月5日在11:02
\ $ \ begingroup \ $
@ Blindman67我喜欢你的建议。我在之前添加了moveup，在循环的末尾进行了计算，但是后来我意识到在开始时它更有意义，却忘记简化它。至于height [j--]，我现在无法测试，但不是rainWater + = maxL-height [i ++]更改表达式，还是在计算maxL-height [i]后应用i ++ ？
\ $ \ endgroup \ $
–加百列·达戈斯托
19年5月5日在20:59
\ $ \ begingroup \ $
@ Gabrield'Agosto在计算表达式后执行i ++递增和i–递减。例如，如果j = 1，则maxR-height [j--]将在索引1处获得高度。但是，这是一个很小的变化，您最好坚持自己喜欢的东西。
\ $ \ endgroup \ $
– Blindman67
19 Jun 6 '19在0:44
#7 楼
我喜欢以类似于绘制图像的方式来执行此操作的想法，也就是说，创建与您上面的图像有些相似的数据结构，然后使用该数据结构来计算哪些空间坚持下去。这不是代码审查的全部内容，而是一种表示做同一件事的替代方法的说明（此处提供了许多答案）。我不知道我会说更好，但是至少对我来说很有趣。
代码将size数组映射到一个由1和0组成的网格，修剪所有初始的0，并然后计算每行还剩多少。我相当确定这将始终给出正确的结果，但是那样的话，我可能会错过一些东西。
const data = [1,0,2,1,0,1,3,2,1,2,1];
const sizesToRows = sizeArray => [...Array(Math.max(...sizeArray))]
.map((_, i) => sizeArray.map(s => s > i ? 1 : 0))
const trimArray = condition => array => array.slice(
array.findIndex(condition),
array.length - array
.reduce((ary, ele) => {ary.unshift(ele); return ary}, [])
.findIndex(condition)
);
const removeLeadingAndTrailingZeroes = trimArray(x => x !== 0);
const countConditionMatches = condition => array => array
.reduce((p, c) => condition(c) ? p + 1 : p, 0);
const countZeroes = countConditionMatches(x => x === 0);
const sum = (p, c) => p + c
const result = sizesToRows(data)
.map(removeLeadingAndTrailingZeroes)
.map(countZeroes)
.reduce(sum, 0);
console.dir(result)
评论
\ $ \ begingroup \ $
有一个错误，如果数组为空，则Array.reduce第二个可选参数不是可选的。例如[0] .reduce（sum）起作用，而[] .reduce（sum）会引发错误，您需要为空数组提供init值。
\ $ \ endgroup \ $
– Blindman67
19年5月5日上午11:15
\ $ \ begingroup \ $
@ Blindman67谢谢，好地方，我已经更新了
\ $ \ endgroup \ $
– OliverRadini
19年5月5日在11:45
评论
嗯...马科斯是谁？将那个图像贡献给leetcode的人。 （我只是从leetcode复制了说明）@Justin