雨水輸送

Q:高さを入力し、雨上がりにどれだけの水が溜まるかを計算します。

ex)[1,0,2,0,1,1,3]->5(図示)

プール1:ダブルポインタを最大値に移動

def trap(height):
   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

両ポインタを両端から、各ポインタが右側にある最大値を比較し、右側が高い場合は左ポインタを1マス右に移動し、左ポインタの最大値が高い場合は右ポインタを左に移動します.

ポインタを横に移動するたびに、そのときの最大値と現在のポインタの高さ値からボリューム変数値が減算されます.

の例では、右ポインタの最大値は3であり、総最大値と同じであるため、左ポインタのみが右に移動し、体積値に積載可能な雨水を加えたときに移動する.

ポインタに遭遇した場合、左と右の値は同じであるため、重複文は終了し、その値が返されます.

プール2:スタック

def trap(height):
    stack = []
    volume = 0
    
    for i in range(len(height)):
        
        # 현재 높이가 이전 높이보다 높을 때 수행되는 반복문
        while stack and height[i] > height[stack[-1]]:
            top = stack.pop()
            
            # len(stack)이 0일 경우 break
            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
    

デフォルトでは、for文はスタックリストにスタックごとにインデックスを追加する最初の繰り返し文です.

スタックが空のリストではなく、インデックスが右にある場合、while文が実行されます.

while文が実行されると、スタックの最後の値が失われtopに格納されます.

値を

からtopに減算すると、スタックは空のリストではなく、ボリュームに値が追加されます.

距離は、現在のインデックスとスタック上の最後の値リストの1から減算された値として指定され、高さが2つの高さの最小値と最上位値とで指定されたときの高さ値の差として指定されます.

距離*高さの値がボリューム値に追加されます.

while文が完了した場合は、while文の条件がtrueであるかどうかを再確認し、trueである場合はスタックを再実行します.

体積値は下図

の順に大きくなります.(一度に3,4,5を格納します.)

2つのプールの時間複雑度はO(n)であり,実行時間は同等であった.