Skip to content

Commit 7fa9085

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0042. Trapping Rain Water
1 parent ea7aca5 commit 7fa9085

File tree

6 files changed

+224
-89
lines changed

6 files changed

+224
-89
lines changed

‎solution/0000-0099/0042.Trapping Rain Water/README.md

Lines changed: 79 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -61,17 +61,14 @@ class Solution:
6161
if n < 3:
6262
return 0
6363

64-
left_max = [height[0]] * n
64+
lmx, rmx = [height[0]] * n, [height[n - 1]] * n
6565
for i in range(1, n):
66-
left_max[i] = max(left_max[i - 1], height[i])
67-
68-
right_max = [height[n - 1]] * n
69-
for i in range(n - 2, -1, -1):
70-
right_max[i] = max(right_max[i + 1], height[i])
71-
66+
lmx[i] = max(lmx[i - 1], height[i])
67+
rmx[n - 1 - i] = max(rmx[n - i], height[n - 1 - i])
68+
7269
res = 0
7370
for i in range(n):
74-
res += min(left_max[i], right_max[i]) - height[i]
71+
res += min(lmx[i], rmx[i]) - height[i]
7572
return res
7673
```
7774

@@ -82,27 +79,91 @@ class Solution:
8279
```java
8380
class Solution {
8481
public int trap(int[] height) {
85-
int n;
86-
if ((n = height.length) < 3) return 0;
82+
int n = height.length;
83+
if (n < 3) {
84+
return 0;
85+
}
8786

88-
int[] leftMax = new int[n];
89-
leftMax[0] = height[0];
87+
int[] lmx = new int[n];
88+
int[] rmx = new int[n];
89+
lmx[0] = height[0];
90+
rmx[n - 1] = height[n - 1];
9091
for (int i = 1; i < n; ++i) {
91-
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
92+
lmx[i] = Math.max(lmx[i - 1], height[i]);
93+
rmx[n - 1 - i] = Math.max(rmx[n - i], height[n - i - 1]);
94+
}
95+
96+
int res = 0;
97+
for (int i = 0; i < n; ++i) {
98+
res += Math.min(lmx[i], rmx[i]) - height[i];
9299
}
100+
return res;
101+
}
102+
}
103+
```
93104

94-
int[] rightMax = new int[n];
95-
rightMax[n - 1] = height[n - 1];
96-
for (int i = n - 2; i >= 0; --i) {
97-
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
105+
### **C++**
106+
107+
```cpp
108+
class Solution {
109+
public:
110+
int trap(vector<int>& height) {
111+
int n = height.size();
112+
if (n < 3) {
113+
return 0;
98114
}
99115

116+
vector<int> lmx(n, height[0]);
117+
vector<int> rmx(n, height[n - 1]);
118+
for (int i = 1; i < n; ++i) {
119+
lmx[i] = max(lmx[i - 1], height[i]);
120+
rmx[n - 1 - i] = max(rmx[n - i], height[n - 1 - i]);
121+
}
122+
100123
int res = 0;
101124
for (int i = 0; i < n; ++i) {
102-
res += Math.min(leftMax[i], rightMax[i]) - height[i];
125+
res += min(lmx[i], rmx[i]) - height[i];
103126
}
104127
return res;
105128
}
129+
};
130+
```
131+
132+
### **Go**
133+
134+
```go
135+
func trap(height []int) int {
136+
n := len(height)
137+
if n < 3 {
138+
return 0
139+
}
140+
141+
lmx, rmx := make([]int, n), make([]int, n)
142+
lmx[0], rmx[n-1] = height[0], height[n-1]
143+
for i := 1; i < n; i++ {
144+
lmx[i] = max(lmx[i-1], height[i])
145+
rmx[n-1-i] = max(rmx[n-i], height[n-1-i])
146+
}
147+
148+
res := 0
149+
for i := 0; i < n; i++ {
150+
res += min(lmx[i], rmx[i]) - height[i]
151+
}
152+
return res
153+
}
154+
155+
func max(a, b int) int {
156+
if a > b {
157+
return a
158+
}
159+
return b
160+
}
161+
162+
func min(a, b int) int {
163+
if a < b {
164+
return a
165+
}
166+
return b
106167
}
107168
```
108169

‎solution/0000-0099/0042.Trapping Rain Water/README_EN.md

Lines changed: 79 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -45,17 +45,14 @@ class Solution:
4545
if n < 3:
4646
return 0
4747

48-
left_max = [height[0]] * n
48+
lmx, rmx = [height[0]] * n, [height[n - 1]] * n
4949
for i in range(1, n):
50-
left_max[i] = max(left_max[i - 1], height[i])
51-
52-
right_max = [height[n - 1]] * n
53-
for i in range(n - 2, -1, -1):
54-
right_max[i] = max(right_max[i + 1], height[i])
55-
50+
lmx[i] = max(lmx[i - 1], height[i])
51+
rmx[n - 1 - i] = max(rmx[n - i], height[n - 1 - i])
52+
5653
res = 0
5754
for i in range(n):
58-
res += min(left_max[i], right_max[i]) - height[i]
55+
res += min(lmx[i], rmx[i]) - height[i]
5956
return res
6057
```
6158

@@ -64,27 +61,91 @@ class Solution:
6461
```java
6562
class Solution {
6663
public int trap(int[] height) {
67-
int n;
68-
if ((n = height.length) < 3) return 0;
64+
int n = height.length;
65+
if (n < 3) {
66+
return 0;
67+
}
6968

70-
int[] leftMax = new int[n];
71-
leftMax[0] = height[0];
69+
int[] lmx = new int[n];
70+
int[] rmx = new int[n];
71+
lmx[0] = height[0];
72+
rmx[n - 1] = height[n - 1];
7273
for (int i = 1; i < n; ++i) {
73-
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
74+
lmx[i] = Math.max(lmx[i - 1], height[i]);
75+
rmx[n - 1 - i] = Math.max(rmx[n - i], height[n - i - 1]);
76+
}
77+
78+
int res = 0;
79+
for (int i = 0; i < n; ++i) {
80+
res += Math.min(lmx[i], rmx[i]) - height[i];
7481
}
82+
return res;
83+
}
84+
}
85+
```
7586

76-
int[] rightMax = new int[n];
77-
rightMax[n - 1] = height[n - 1];
78-
for (int i = n - 2; i >= 0; --i) {
79-
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
87+
### **C++**
88+
89+
```cpp
90+
class Solution {
91+
public:
92+
int trap(vector<int>& height) {
93+
int n = height.size();
94+
if (n < 3) {
95+
return 0;
8096
}
8197

98+
vector<int> lmx(n, height[0]);
99+
vector<int> rmx(n, height[n - 1]);
100+
for (int i = 1; i < n; ++i) {
101+
lmx[i] = max(lmx[i - 1], height[i]);
102+
rmx[n - 1 - i] = max(rmx[n - i], height[n - 1 - i]);
103+
}
104+
82105
int res = 0;
83106
for (int i = 0; i < n; ++i) {
84-
res += Math.min(leftMax[i], rightMax[i]) - height[i];
107+
res += min(lmx[i], rmx[i]) - height[i];
85108
}
86109
return res;
87110
}
111+
};
112+
```
113+
114+
### **Go**
115+
116+
```go
117+
func trap(height []int) int {
118+
n := len(height)
119+
if n < 3 {
120+
return 0
121+
}
122+
123+
lmx, rmx := make([]int, n), make([]int, n)
124+
lmx[0], rmx[n-1] = height[0], height[n-1]
125+
for i := 1; i < n; i++ {
126+
lmx[i] = max(lmx[i-1], height[i])
127+
rmx[n-1-i] = max(rmx[n-i], height[n-1-i])
128+
}
129+
130+
res := 0
131+
for i := 0; i < n; i++ {
132+
res += min(lmx[i], rmx[i]) - height[i]
133+
}
134+
return res
135+
}
136+
137+
func max(a, b int) int {
138+
if a > b {
139+
return a
140+
}
141+
return b
142+
}
143+
144+
func min(a, b int) int {
145+
if a < b {
146+
return a
147+
}
148+
return b
88149
}
89150
```
90151

‎solution/0000-0099/0042.Trapping Rain Water/Solution.cpp

Lines changed: 16 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -1,38 +1,22 @@
11
class Solution {
22
public:
33
int trap(vector<int>& height) {
4-
int len = height.size();
5-
if(len == 0 || len == 1)return 0;
6-
7-
int slow = 0;
8-
int fast = 1;
9-
10-
int stopPoint;
11-
12-
int total = 0;
13-
int bottom;
14-
int tmp = 0;
15-
while(fast < len){
16-
//每次更新stopPoint
17-
stopPoint = fast;
18-
while(fast < len && height[fast] <= height[slow]){
19-
if(height[fast] > height[stopPoint])
20-
stopPoint = fast;
21-
fast++;
22-
}
23-
24-
//越界了要回到stopPoint
25-
if(fast >= len)fast = stopPoint;
4+
int n = height.size();
5+
if (n < 3) {
6+
return 0;
7+
}
268

27-
tmp = 0;
28-
bottom = min(height[slow],height[fast]);
29-
for(int i = slow+1;i<fast;i++){
30-
tmp += bottom - height[i];
31-
}
32-
slow = fast;
33-
total += tmp;
34-
fast++;
9+
vector<int> lmx(n, height[0]);
10+
vector<int> rmx(n, height[n - 1]);
11+
for (int i = 1; i < n; ++i) {
12+
lmx[i] = max(lmx[i - 1], height[i]);
13+
rmx[n - 1 - i] = max(rmx[n - i], height[n - 1 - i]);
14+
}
15+
16+
int res = 0;
17+
for (int i = 0; i < n; ++i) {
18+
res += min(lmx[i], rmx[i]) - height[i];
3519
}
36-
return total;
37-
}
20+
return res;
21+
}
3822
};

‎solution/0000-0099/0042.Trapping Rain Water/Solution.go

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
func trap(height []int) int {
2+
n := len(height)
3+
if n < 3 {
4+
return 0
5+
}
6+
7+
lmx, rmx := make([]int, n), make([]int, n)
8+
lmx[0], rmx[n-1] = height[0], height[n-1]
9+
for i := 1; i < n; i++ {
10+
lmx[i] = max(lmx[i-1], height[i])
11+
rmx[n-1-i] = max(rmx[n-i], height[n-1-i])
12+
}
13+
14+
res := 0
15+
for i := 0; i < n; i++ {
16+
res += min(lmx[i], rmx[i]) - height[i]
17+
}
18+
return res
19+
}
20+
21+
func max(a, b int) int {
22+
if a > b {
23+
return a
24+
}
25+
return b
26+
}
27+
28+
func min(a, b int) int {
29+
if a < b {
30+
return a
31+
}
32+
return b
33+
}

‎solution/0000-0099/0042.Trapping Rain Water/Solution.java

Lines changed: 12 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,23 +1,22 @@
11
class Solution {
22
public int trap(int[] height) {
3-
int n;
4-
if ((n = height.length) < 3) return 0;
5-
6-
int[] leftMax = new int[n];
7-
leftMax[0] = height[0];
8-
for (int i = 1; i < n; ++i) {
9-
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
3+
int n = height.length;
4+
if (n < 3) {
5+
return 0;
106
}
117

12-
int[] rightMax = new int[n];
13-
rightMax[n - 1] = height[n - 1];
14-
for (int i = n - 2; i >= 0; --i) {
15-
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
8+
int[] lmx = new int[n];
9+
int[] rmx = new int[n];
10+
lmx[0] = height[0];
11+
rmx[n - 1] = height[n - 1];
12+
for (int i = 1; i < n; ++i) {
13+
lmx[i] = Math.max(lmx[i - 1], height[i]);
14+
rmx[n - 1 - i] = Math.max(rmx[n - i], height[n - i - 1]);
1615
}
17-
16+
1817
int res = 0;
1918
for (int i = 0; i < n; ++i) {
20-
res += Math.min(leftMax[i], rightMax[i]) - height[i];
19+
res += Math.min(lmx[i], rmx[i]) - height[i];
2120
}
2221
return res;
2322
}

‎solution/0000-0099/0042.Trapping Rain Water/Solution.py

Lines changed: 5 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -4,15 +4,12 @@ def trap(self, height: List[int]) -> int:
44
if n < 3:
55
return 0
66

7-
left_max = [height[0]] * n
7+
lmx, rmx = [height[0]] * n, [height[n - 1]] * n
88
for i in range(1, n):
9-
left_max[i] = max(left_max[i - 1], height[i])
10-
11-
right_max = [height[n - 1]] * n
12-
for i in range(n - 2, -1, -1):
13-
right_max[i] = max(right_max[i + 1], height[i])
9+
lmx[i] = max(lmx[i - 1], height[i])
10+
rmx[n - 1 - i] = max(rmx[n - i], height[n - 1 - i])
1411

1512
res = 0
1613
for i in range(n):
17-
res += min(left_max[i], right_max[i]) - height[i]
18-
return res
14+
res += min(lmx[i], rmx[i]) - height[i]
15+
return res

0 commit comments

Comments
 (0)