https://leetcode.com/problems/trapping-rain-water
Trapping Rain Water - LeetCode
Can you solve this real interview question? 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: [https://assets.leetcode.com/upl
leetcode.com
1. two pointer로 접근하기
왼쪽과 오른쪽에서 각각 이동한다.
왼쪽 방향의 최대치 = 현재 높이, 왼쪽 방향 최대치와 비교한 것의 max값
오른쪽 방향의 최대치 = 현재 높이, 오른쪽 방향 최대치와 비교한 것의 max값
왼쪽 방향의 최대치, 오른 방향의 최대치를 비교하면서
물의 넓이를 누적한다.
2. stack 누적
스택에는 현재 위치를 누적해나가다가
현재 높이가 스택 TOP의 높이보다 크게 될 경우
스택의 TOP 과 현재까지의 길이를 구하고
높이를 스택과 현재의 높이 중 낮은 값으로 결정하여 길이 * 높이로 물의 양을 누적시킨다.
'알고리즘 > Array' 카테고리의 다른 글
| two sum (0) | 2023.10.02 |
|---|---|
| Longest Palindrome Substring (0) | 2023.10.01 |
| 그룹 애너그램 (0) | 2023.09.29 |
| 가장 흔한 단어 (0) | 2023.09.29 |
| 로그 파일 정렬하기 (0) | 2023.09.28 |
