Heading

42.接雨水 (opens new window)

Tags: algorithms amazon apple bloomberg google twitter zenefits array two-pointers stack

Langs: c cpp csharp dart elixir erlang golang java javascript kotlin php python python3 racket ruby rust scala swift typescript

• algorithms
• Hard (63.28%)
• Likes: 5071
• Dislikes: -
• Total Accepted: 901.1K
• Total Submissions: 1.4M
• Testcase Example: '[0,1,0,2,1,0,1,3,2,1,2,1]'

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

 

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

/*
 * @lc app=leetcode.cn id=42 lang=javascript
 *
 * [42] 接雨水
 * 乱七八糟解出来的……，固定左指针寻找下一个右侧边际
 */

// @lc code=start
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let i = 0
  let j = 0
  let sum = 0

  while (i < height.length) {
    if (height[i] > 0) {
      j = i + 1
      let tmpHeight = 0
      let tmpMax = 0
      let rightIndex = 0
      while (j < height.length && height[j] < height[i]) {
        if (height[j] > tmpMax) {
          tmpMax = height[j]
          rightIndex = j
        }
        tmpHeight += height[j++]
      }
      if (j < height.length) {
        rightIndex = j
      } else if (rightIndex > 0) {
        let k = rightIndex
        while (k < j) {
          tmpHeight -= height[k++]
        }
      }

      if (rightIndex > 0) {
        sum += (rightIndex - i - 1) * Math.min(height[i], height[rightIndex]) - tmpHeight
        i = rightIndex
        continue
      }
    }
    i++
  }
  return sum
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=42 lang=javascript
 *
 * [42] 接雨水
 * 双指针
 */

// @lc code=start
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let left = 0
  let right = height.length - 1
  let leftMax = 0
  let rightMax = 0
  let sum = 0
  while (left < right) {
    leftMax = Math.max(leftMax, height[left])
    rightMax = Math.max(rightMax, height[right])

    if (height[left] < height[right]) {
      sum += leftMax - height[left++]
    } else {
      sum += rightMax - height[right--]
    }
  }
  return sum
}
// @lc code=end