높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라
입력:
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
출력: 6
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
def trap(height):
if len(height) < 1:
return 0
water = 0
left = 0
right = len(height) - 1
top = height.index(max(height))
left_max = height[left]
right_max = height[right]
while left < right:
left_max = max(height[left], left_max)
right_max = max(height[right], right_max)
if left < top:
water += left_max - height[left]
left += 1
if right > top:
water += right_max - height[right]
right -= 1
return water
trap(height)
6
Accepted 48 ms 14.7 MB python3
def trap(height):
if len(height) < 1:
return 0
water = 0
left = 0
right = len(height) - 1
left_max = height[left]
right_max = height[right]
while left < right:
left_max = max(height[left], left_max)
right_max = max(height[right], right_max)
if left_max <= right_max:
water += left_max - height[left]
left += 1
else:
water += right_max - height[right]
right -= 1
return water
Accepted 52 ms 14.8 MB python3
def trap(height):
stack = []
volume = 0
for i in range(len(height)):
while stack and height[i] > height[stack[-1]]:
top = stack.pop()
if not len(stack):
break
distance = i - stack[-1] - 1
waters = min(height[i], height[stack[-1]]) - height[top]
volume += distance * waters
stack.append(i)
return volume
trap(height)
6
Accepted 56 ms 14.8 MB python3