Trapping Rain Water - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
|
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
|
def trap(height) -> int:
if not height:
return 0
volume = 0
start = 0 # 0
end = len(height) - 1 # 11
start_max = height[start] # 0
end_max = height[end] # 1
while start < end:
# 최대 기둥 높이
start_max = max(height[start], start_max)
end_max = max(height[end], end_max)
print(f'{start} < {end}')
print(f'start_max = {start_max}, end_max = {end_max}')
if start_max <= end_max:
print(f'[start] volume({volume}) += start_max({start_max}) - height[{start}](={height[start]})')
volume += start_max - height[start]
print(volume)
start += 1
else:
print(f'[end] volume({volume}) += emd_max({end_max}) - height[{end}](={height[end]})')
volume += end_max - height[end]
print(volume)
end -= 1
print()
return volume
trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])
# trap([0,1,0,])
# start 와 end 의 높이가 최소 타이를 이루어야만 volume 이 증가한다.
|
cs |
'알고리즘 문제풀이 with 파이썬 > LeetCode' 카테고리의 다른 글
| [배열] Array Partition I (0) | 2021.09.10 |
|---|---|
| [배열] 3Sum (0) | 2021.09.09 |
| [배열] Two Sum (0) | 2021.09.04 |
| [문자열] Longest Palindromic Substring (0) | 2021.09.03 |
| [문자열] Group Anagrams (0) | 2021.09.01 |