FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/problems/src/array/PourWater.java at master · KindleBooks66/leetcode · GitHub
Uh oh!
There was an error while loading.
Please reload this page
.
KindleBooks66
/
leetcode
Public
forked from
gouthampradhan/leetcode
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
problems
/
src
/
array
/
PourWater.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
116 lines (113 loc) · 4.35 KB
Breadcrumbs
leetcode
/
problems
/
src
/
array
/
PourWater.java
Copy path
File metadata and controls
116 lines (113 loc) · 4.35 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package
array
;
/**
* Created by gouthamvidyapradhan on 03/02/2018. We are given an elevation map, heights[i]
* representing the height of the terrain at that index. The width at each index is 1. After V units
* of water fall at index K, how much water is at each index?
*
* <p>Water first drops at index K and rests on top of the highest terrain or water at that index.
* Then, it flows according to the following rules:
*
* <p>If the droplet would eventually fall by moving left, then move left. Otherwise, if the droplet
* would eventually fall by moving right, then move right. Otherwise, rise at it's current position.
* Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in
* that direction. Also, "level" means the height of the terrain plus any water in that column. We
* can assume there's infinitely high terrain on the two sides out of bounds of the array. Also,
* there could not be partial water being spread out evenly on more than 1 grid block - each unit of
* water has to be in exactly one block.
*
* <p>Example 1: Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3 Output: [2,2,2,3,2,2,2] Explanation:
* # # # # ## # ### ######### 0123456 <- index
*
* <p>The first drop of water lands at index K = 3:
*
* <p># # # w # ## # ### ######### 0123456
*
* <p>When moving left or right, the water can only move to the same level or a lower level. (By
* level, we mean the total height of the terrain plus any water in that column.) Since moving left
* will eventually make it fall, it moves left. (A droplet "made to fall" means go to a lower height
* than it was at previously.)
*
* <p># # # # ## w# ### ######### 0123456
*
* <p>Since moving left will not make it fall, it stays in place. The next droplet falls:
*
* <p># # # w # ## w# ### ######### 0123456
*
* <p>Since the new droplet moving left will eventually make it fall, it moves left. Notice that the
* droplet still preferred to move left, even though it could move right (and moving right makes it
* fall quicker.)
*
* <p># # # w # ## w# ### ######### 0123456
*
* <p># # # # ##ww# ### ######### 0123456
*
* <p>After those steps, the third droplet falls. Since moving left would not eventually make it
* fall, it tries to move right. Since moving right would eventually make it fall, it moves right.
*
* <p># # # w # ##ww# ### ######### 0123456
*
* <p># # # # ##ww#w### ######### 0123456
*
* <p>Finally, the fourth droplet falls. Since moving left would not eventually make it fall, it
* tries to move right. Since moving right would not eventually make it fall, it stays in place:
*
* <p># # # w # ##ww#w### ######### 0123456
*
* <p>The final answer is [2,2,2,3,2,2,2]:
*
* <p># ####### ####### 0123456 Example 2: Input: heights = [1,2,3,4], V = 2, K = 2 Output:
* [2,3,3,4] Explanation: The last droplet settles at index 1, since moving further left would not
* cause it to eventually fall to a lower height. Example 3: Input: heights = [3,1,3], V = 5, K = 1
* Output: [4,4,4] Note:
*
* <p>heights will have length in [1, 100] and contain integers in [0, 99]. V will be in range [0,
* 2000]. K will be in range [0, heights.length - 1].
*
* <p>Solution: Check first left and then right to see if there are any lower levels, if yes then
* drop the water at this point. Else maintain the drop at the start position
*/
public
class
PourWater
{
/**
* Main method
*
* @param args
* @throws Exception
*/
public
static
void
main
(
String
[]
args
)
throws
Exception
{
int
[]
A
= {
2
,
1
,
1
,
2
,
1
,
2
,
2
};
int
[]
result
=
new
PourWater
().
pourWater
(
A
,
4
,
3
);
for
(
int
i
:
result
) {
System
.
out
.
print
(
i
+
" "
);
}
}
public
int
[]
pourWater
(
int
[]
heights
,
int
V
,
int
K
) {
while
(
V
-- >
0
) {
heights
[
K
] +=
1
;
int
index
=
K
;
int
min
=
heights
[
K
];
for
(
int
i
=
K
-
1
;
i
>=
0
;
i
--) {
if
(
heights
[
i
] +
1
>
min
) {
break
;
}
else
if
(
heights
[
i
] +
1
<
min
) {
min
=
heights
[
i
] +
1
;
index
=
i
;
}
}
if
(
index
==
K
) {
for
(
int
i
=
K
+
1
;
i
<
heights
.
length
;
i
++) {
if
(
heights
[
i
] +
1
>
min
) {
break
;
}
else
if
(
heights
[
i
] +
1
<
min
) {
min
=
heights
[
i
] +
1
;
index
=
i
;
}
}
}
if
(
index
!=
K
) {
heights
[
K
]--;
heights
[
index
]++;
}
}
return
heights
;
}
}
Back
|
FazBrowse Home
|
New Git URL