LeetCode 42 - Trapping Rain Water (Hard)

 

💡 문제

LeetCode - 42번

 

🎯 풀이 과정

웅덩이를 찾기 위해서는 단조감소 구간을 알아야합니다.

O(n) 에 이를 알 수 있는 방법이 무엇일까요?

 

이를 위해 monotonic stack을 활용할 수 있습니다.

height 의 인덱스를 i 라고 하겠습니다.

 

(a) height[i] 가 stack top 보다 작다면 그냥 push 합니다.
(b) stack top 값보다 크거나 같다면 push 하기전에 stack 에서 height[i] 보다 작거나 같은 값을 가지는 요소들을 모두 pop 합니다.

 

물 웅덩이의 크기를 알려면 높이 * 너비 를 알아야합니다.

너비는 index 값으로 쉽게 알 수 있고, 높이는 다음과 같이 구할 수 있습니다.

min(height[stack[top-1]], height[i]) - height[stack[top]]

 

필요한 값들을 알았으니, 이제 위 과정들을 배열의 끝에 도달할때까지 반복해줍니다.

 

👨‍💻 코드

/**
 * @param {number[]} heights
 * @return {number}
 */
var trap = function(heights) {
    let answer = 0

    const stack = []

    for (let idx = 0; idx < heights.length; idx += 1) {
        if (stack.length <= 0 || heights[stack.at(-1)] > heights[idx]) {
            stack.push(idx)
            continue
        }

        while (stack.length > 0 && heights[stack.at(-1)] <= heights[idx]) {
            const top = stack.at(-1)
            stack.pop()

            if (stack.length <= 0) {
                break
            }

            const width = idx - stack.at(-1) - 1
            const height = Math.min(heights[stack.at(-1)], heights[idx]) - heights[top]

            answer += (width * height)
        }

        stack.push(idx)
    }

    return answer
};