[Leetcode] 42. Trapping Rain Water
7909 ワード
「Pythonアルゴリズムインタビュー」という本でコードテストを勉強するとき、解答を見ても理解できないところがあるので、先に記録して、後で理解を残しておきましょう. Trapping Rain Water
高さを入力し、雨上がりにどれだけの水が溜まるかを計算します.
この方法は別のブログ記事で理解された.
この方法は他のブログの文章を見ても読めません...
高さを入力し、雨上がりにどれだけの水が溜まるかを計算します.
最初の方法ポインタを最大値に移動
この方法は別のブログ記事で理解された.
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
volume = 0
left, right = 0, len(height)-1
left_max, right_max = height[left], height[right]
while left < right:
left_max, right_max = max(height[left], left_max), max(height[right], right_max)
# 더 높은 쪽을 향해 투 포인터 이동
if left_max <= right_max:
volume += left_max - height[left]
left += 1
else:
volume += right_max -height[right]
right -= 1
return volume
第2の方法スタッキング
この方法は他のブログの文章を見ても読めません...
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]]: # 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
Reference
この問題について([Leetcode] 42. Trapping Rain Water), 我々は、より多くの情報をここで見つけました https://velog.io/@tnqls1211v/Leetcode-42.-Trapping-Rain-Waterテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol