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

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
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
1. 투 포인터를 최대로 이용
O(n^2)으로 풀면 너무 비효율적이다. 그래서 투포인터를 이용한다.
양쪽 벽을 확인하고 더 높은쪽 벽을 기준으로 세워두고 그쪽으로 계속 향하면서 물을 채워나간다.
어렵다 😖 leetcod에도 hard로 분류되어있다.
onlybooks/algorithm-interview
<파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트. Contribute to onlybooks/algorithm-interview development by creating an account on GitHub.
github.com
2. 스택을 이용
onlybooks/algorithm-interview
<파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트. Contribute to onlybooks/algorithm-interview development by creating an account on GitHub.
github.com

거리를 구하고, 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
