LeetCode Trapping Rain Water (JavaScript), Two pointer

링크 : https://leetcode.com/problems/trapping-rain-water/description/

문제 설명

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.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

---

문제 풀이

접근 방법 (투 포인터를 이용하여 해결)

1. 맨 왼쪽, 맨 오른쪽의 포인터를 2개 두어 범위를 좁혀 오면서 계산
   • 범위를 좁히는 기준 -> 둘 중 더 작은 곳을 이동
2. 해당 위치에서 계산을 하기 위해 leftMax, rightMax를 설정 -> 어떠한 높이 기준으로 계산을 할 건지 필요하기 때문
   
   • 만약 Max 값보다 현재 위치가 더 클 경우 Max값 조정
   • 더 작다면 물을 채울 공간이 있다는 의미이므로 계산 (Max값 - 현재 위치의 높이)
   • 위치 이동

로직 진행에 따른 변화 (빨강 : 이전, 파랑 : 이후)

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let [left, right] = [0, height.length - 1];
    let [leftMax, rightMax] = [0, 0];
    let answer = 0;

    while (left < right) {
        if (height[left] <= height[right]) {
            if (height[left] > leftMax) {
                leftMax = height[left];
            } else {
                answer += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] > rightMax) {
                rightMax = height[right];
            } else {
                answer += rightMax - height[right];
            }
            right--;
        }
    }

    return answer;
};

---

결론

해당 문제는 O(n)의 시간 복잡도로 해결할 수 있고, 이를 위해 투 포인터 알고리즘을 활용하여 풀어야 한다.

단순히 left, right의 두 개의 포인터만 이용해서 해결할 수 없고, 각 위치에서 어떠한 기준으로 계산할지에 대한 값이 필요

따라서 왼쪽, 오른쪽 각 Max값을 저장해 특정 위치에서 높이차이를 이용해 계산을 해야함.