[파이썬 알고리즘 인터뷰] 빗물 트래핑

github.com/onlybooks/algorithm-interview

아.. 이거 너무 어렵단

---

42. 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:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

---

Trapping Rain Water - LeetCode

 

1. 투 포인터를 최대로 이용

O(n^2)으로 풀면 너무 비효율적이다. 그래서 투포인터를 이용한다.

양쪽 벽을 확인하고 더 높은쪽 벽을 기준으로 세워두고 그쪽으로 계속 향하면서 물을 채워나간다.

어렵다 😖 leetcod에도 hard로 분류되어있다.

 

onlybooks/algorithm-interview

 

 2. 스택을 이용

onlybooks/algorithm-interview

[0,1,0,2,1,0,1,3,2,1,2,1]

거리를 구하고, stack을 이용하였으니 그전에 가장 작았던 벽과의 차이를 구해서 물을 채우는 식으로.. 아래 그림처럼 채워지는 것인듯!

i: 3 stack[-1]: 1
distance: 1
height[i]: 2 height[stack[-1]] 1 height[top]: 0 top: 2
waters: 1


i: 6 stack[-1]: 4
distance: 1
height[i]: 1 height[stack[-1]] 1 height[top]: 0 top: 5
waters: 1


i: 7 stack[-1]: 4
distance: 2
height[i]: 3 height[stack[-1]] 1 height[top]: 1 top: 6
waters: 0


i: 7 stack[-1]: 3
distance: 3
height[i]: 3 height[stack[-1]] 2 height[top]: 1 top: 4
waters: 1


i: 10 stack[-1]: 8
distance: 1
height[i]: 2 height[stack[-1]] 2 height[top]: 1 top: 9
waters: 1