esc to dismiss

42. 接雨水

题目

给定 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

解体思路

这是一道 单调栈 题目。

可以这样入栈,从左向右,如果遇到柱子更短的则入栈,遇到长的则出栈,即单调栈是一个递减的单调栈。而出栈的时候可以计算本次出栈的形成容器的大小,因此可以计算出这个容器能盛多少雨水。而同时要更新下它们的新高度(因为空的部分已经计算了雨水了,因此要将它们填满。)

而最后,要考虑还在单调栈内的柱子,统计下它们能盛的雨水。

func trap(height []int) int {
    var mono []int
    rain := 0

    for i, v := range height {
        left := -1
        for len(mono) > 0 && v >= height[mono[len(mono)-1]] {
            left = mono[len(mono)-1]
            mono = mono[:len(mono)-1]
        }

        if left >= 0 {
            leftHeight := height[left]
            for j := left; j < i; j++ {
                rain += leftHeight - height[j]
                height[j] = leftHeight
            }
        }

        mono = append(mono, i)
    }

  // 计算剩余在单调栈内的柱子能盛的雨水
  for i := len(mono) - 1; i > 0; i-- {
        for j := mono[i]; j > mono[i-1]; j-- {
            rain += height[mono[i]] - height[j]
        }
    }

    return rain
}

经验教训

第一次提交没有考虑剩余在单调栈内的柱子。

x