42. 接雨水

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  const len = height.length
  if (len <= 2) return 0 // 可以不加
  const st = [] // 存着下标，计算的时候用下标对应的柱子高度
  st.push(0)
  let sum = 0
  for (let i = 1; i < len; i++) {
    while (st.length !== 0 && height[i] > height[st[st.length - 1]]) {
      let mid = st[st.length - 1]
      st.pop()
      if (st.length !== 0) {
        let h = Math.min(height[st[st.length - 1]], height[i]) - height[mid]
        let w = i - st[st.length - 1] - 1 // 注意减一，只求中间宽度
        sum += h * w
      }
    }
    st.push(i)
  }
  return sum
}