[알고리즘] LeetCode - 42. 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 is able to trap after raining.
(번역) 높이를 나타내는 음이 아닌 정수로 구성된 배열이 주어졌을 때 비가 온 후 담기게 될 물의 양을 구하라. 각 bar의 폭은 1이다.

Example:

Input: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

풀이

뭔가 stack을 써야할 것 같은 느낌적인 느낌이 든다.
Stack에 elevation들을 쌓다가 직전 elavation보다 높은 elavation을 만났을 때 기존 스택에 쌓인 bar들을 찾아가며 계산을 하면 되지 않을까!

1) stack에 아무것도 없으면 일단 elevation들을 쌓아준다.
2) 만약 stack에 무언가 있고 현재 elevation이 stack의 top element의 높이보다 크다면, stack의 해당 element를 제거한다.
3) stack에 요소가 존재할 때 까지 차례로 물의 양을 계산한다.

• 양 끝 바의 높이 중 낮은 값에서 양 끝 바의 사이의 바 중 가장 높은 값을 빼주면 해당 구간의 물 높이가 된다.
  4) 만약 현재 bar보다 높은 bar를 만나면 루프를 중단한다.

구현 코드

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  // stack에는 { index: number, val: number } 형태의 object를 담는다.
  const stack = [];
  let answer = 0;

  for (let i = 0; i < height.length; i++) {
    // stack이 비어있지 않고 stack의 top element가 현재 height보다 높은 경우
    if (stack.length && height[i] > stack[stack.length - 1].val) {
      stack.pop(); // 첫 번째 요소 제거
      while (stack.length) {
        const left = stack[stack.length - 1];
        const base = Math.max(...height.slice(left.index + 1, i));
        const localHeight = Math.min(height[i], left.val) - base;
        const width = i - left.index - 1;
        answer += localHeight * width;
        if (left.val >= height[i]) { // 현재 바(height[i])보다 높은 값을 만나면 while loop 중단
          break;
        }
        // stack에서 요소 하나를 제거한다.
        stack.pop();
      }
    }
    // 나머지 경우 stack에 object를 추가해준다.
    stack.push({ index: i, val: height[i] });
  }

  return answer;
};

결과

Runtime: 96 ms, faster than 39.76% of JavaScript online submissions for Trapping Rain Water.
Memory Usage: 38.9 MB, less than 15.36% of JavaScript online submissions for Trapping Rain Water.