0%

LeetCode-接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

接雨水

题目

  上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。

  输入: [0,1,0,2,1,0,1,3,2,1,2,1]

  输出: 6


解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
* @lc app=leetcode.cn id=42 lang=javascript
*
* [42] 接雨水
*
* https://leetcode-cn.com/problems/trapping-rain-water/description/
*
* algorithms
* Hard (40.76%)
* Total Accepted: 8.1K
* Total Submissions: 19.9K
* Testcase Example: '[0,1,0,2,1,0,1,3,2,1,2,1]'
*
* 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
*
*
*
* 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢
* Marcos 贡献此图。
*
* 示例:
*
* 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
* 输出: 6
*
*/
/**
* @param {number[]} height
* @return {number}
*/
var trap = function (height) {
const width = height.length;
let max = min = height[0];
for (let num = 0; num < width; num++) {
if (height[num] > max) {
max = height[num];
};
if (height[num] < min) {
min = height[num];
}
}

let area = 0;
let arr = [];
for (let minN = min; minN < max; minN++) {
arr = [];
for (let i = 0; i < width; i++) {
if (height[i] >= minN + 1) {
arr.push(i);
}
}
for (let arri = 0; arri < arr.length - 1; arri++) {
if (arr[arri + 1] - arr[arri] > 1) {
area += ((arr[arri + 1] - arr[arri]) - 1);
}
}
}

return area;
};

解题思路