雨水洗浄

Trapping Rain Water

デュアルポインタを最大限に活用

最大高さレバーまで、左右の柱ごとに最大高さleft max、right maxと現在の高さの差があり、水の高さ体積が増加した.
左右どちらも高いところに向かっており、ポインタは徐々に真ん中に移動しています.
最も高い棒状点の最大点では,左右のポインタが互いに接触し,O(n)O(n)O(n)の解を行うことができる.

from typing import List

def trap(height: List[int]) -> int:
    if not height:
        return 0
    volumn = 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:
            volumn += left_max - height[left]
            left += 1
        else:
            volumn += right_max - height[right]
            right -= 1
    return volumn
    

if __name__ == "__main__":
    a = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2 ,1]
    print(trap(a))

スタッキング

積み重ねの過程で、現在の高さが前の高さより高い場合、すなわち、変曲点(ここでは柱が高くなる場所、すなわち赤点)を基準に、水の高さを差で充填する.
従来の高さは固定された形態ではなかったため、スタックで埋め続け、変谷点に遭遇するたびに1つ取り出し、以前との違いから出水の高さを算出していた.

from typing import List


def trap(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):  # 스택이 비었다면 skip
                break

            # 이전과의 차이만큼 물 높이 처리
            distance = i - stack[-1] - 1  # 이전 기둥과의 거리 계산
            # 변곡 점과 이전 기둥 중 작은 높이 - 변곡점 이전 지점의 높이
            waters = min(height[i], height[stack[-1]]) - height[top]

            volume += distance * waters

            print(
                f"top: {top}, i: {i}, distance: {distance}, waters: {waters}, volume: {volume}, stack: {stack}"
            )
        stack.append(i)
    return volume


if __name__ == "__main__":
    a = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    print(trap(a))

top: 2, i: 3, distance: 1, waters: 1, volume: 1, stack: [1]
top: 5, i: 6, distance: 1, waters: 1, volume: 2, stack: [3, 4]
top: 6, i: 7, distance: 2, waters: 0, volume: 2, stack: [3, 4]
top: 4, i: 7, distance: 3, waters: 1, volume: 5, stack: [3]
top: 9, i: 10, distance: 1, waters: 1, volume: 6, stack: [7, 8]

これは距離と高さの差に

の距離を乗じて、青い線に対応する水の体積を求めて、次に進む方法です.

参考資料

Pythonアルゴリズムインタビュー