42. Trapping Rain Water

Problem

leetcode 바로가기

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 * 10$^4$
• 0 <= height[i] <= 10$^5$

Solution

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let arr = [];
    let result = 0;
    let index = 0;

  /* 1번 */
  for (let i = 0; i < height.length; i++) {
    if (height[i] >= 1) {
      arr.push(height[i])
      break;
    }
    else {
      index++
    }
  }

  /* 2번 */
  let basis;
  for (let i = index + 1; i < height.length; i++) {
    if (arr[0] <= height[i]) {
      basis = arr[0];
      /* 배열에 있는 요소 계산 */
      for (let j = arr.length - 1; j >= 0; j--) {
        result += basis - arr[j];
      }
      /* 배열 초기화 후 기준점 변경 */
      arr = [];
    }

    arr.push(height[i]);
  }

  /* arr 없을시 바로 출력 */
  if (arr.length <= 0) {
    return result;
  }

  /* 3번 (reverse) - 남은 수가 있을 경우*/
  let basis2 = arr[arr.length - 1];
  let index2 = arr.length - 1;
  /* 마지막 배열부터 반대로 계산 */
  for (let i = arr.length - 2; i >= 0; i--) {
    if (basis2 <= arr[i]) {
      /* 배열에 있는 요소 계산 */
      for (let j = index2; j > i; j--) {
        result += basis2 - arr[j];
        index2--;
      }
      
      basis2 = arr[index2];
    }
  }

  return result;
};