https://leetcode.com/problems/trapping-rain-water/description/
Trapping Rain Water - LeetCode
Trapping Rain Water - Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Example 1: [https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png] Input: he
leetcode.com
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
def trap(self, height: List[int]) -> int:
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
|
cs |
반응형
'python-algorithm' 카테고리의 다른 글
| leetcode 238. Product of Array Except Self (0) | 2023.02.10 |
|---|---|
| leetcode 15. 3Sum (0) | 2023.02.09 |
| 백준 27389 Metronome (0) | 2023.02.09 |
| 백준 27434 팩토리얼 3 (0) | 2023.02.09 |
| 백준 27433 팩토리얼 2 (0) | 2023.02.09 |
댓글