接雨水(leetcode)

接雨水

解法一（按行的思路）

var trap = function (height) {
   const heightArr = height;
   const sortArr = heightArr.slice().sort()
   const maxValue = sortArr[sortArr.length - 1]

   const rowList = []

   for (let i = 1; i <= maxValue; i++) {
      let tempArr = []
      for (let j = 0; j < heightArr.length; j++) {
         if (heightArr[j] >= i) {
            tempArr.push(j)
         }
      }

      rowList.push(tempArr)
   }

   let result = 0;
   for (let g = 0; g < rowList.length; g++) {
      const tempLength = rowList[g].length
      if (tempLength > 1) {
         result += (rowList[g][tempLength - 1] - rowList[g][0] + 1) - tempLength
      }
   }

   return result
};

解法二

当前列的雨水：当前列左边最高柱子和右边最高柱子中的较小的一方 减去 当前列的柱子

var trap = function (height) {

   let leftMax = height[0]
   let result = 0
   for (let i = 1; i < height.length - 1; i++) {
      const item = height[i]

      let rightMax = 0
      for (let j = i + 1; j < height.length; j++) {
         if (height[j] > rightMax) {
            rightMax = height[j]
         }
      }

      if (item < leftMax) {
         if (item < rightMax) {
            result += leftMax > rightMax ? rightMax - item : leftMax - item
         }
      } else {
         leftMax = item
      }
   }
   return result
}