座標hから貯められる水は、右に進んだときの一番高い所と左に進んだ時の一番高い所の小さい方。 これでhardなので平和・・・。
class Solution: def trap(self, height: List[int]) -> int: if len(height)<=1: return 0 N=len(height) maxleft=[0]*N maxright=[0]*N maxleft[0]=height[0] maxright[-1]=height[-1] for h in range(1,N): maxleft[h]=max(maxleft[h-1],height[h]) for h in reversed(range(N-1)): print(h) maxright[h]=max(maxright[h+1],height[h]) print(maxleft,maxright) res=0 for h in range(len(height)): res+=min(max(maxleft[h]-height[h],0),max(maxright[h]-height[h],0)) return res