接雨水

力扣 42. 接雨水

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

方案一：垂直方向每一竖计算能接住的雨水量（前缀和算法）。

func trap(height []int) int {
    n := len(height)
    // 前缀最大值数组和后缀最大值数组
    preMax, sufMax := make([]int, n), make([]int, n)

    // 计算前缀最大值
    preMax[0] = height[0]
    for i := 1;i < n; i++ {
        preMax[i] = max(preMax[i - 1], height[i])
    }

    // 计算后缀最大值
    sufMax[n - 1] = height[n - 1]
    for i := n - 2; i >=0; i-- {
        sufMax[i] = max(sufMax[i + 1], height[i])
    }

    ans := 0
    // 遍历数组，掠过第一个和最后一个，因为其必定无法接到雨水
    for i := 1; i <= n - 2; i++ {
        // 前前缀最大值和后缀最大值中较小的部分，取较高的部分会导致雨水从较低的部分漏走
        ans += min(preMax[i], sufMax[i]) - height[i]
    }    
    return ans
}

func max(a, b int) int {
    if a > b {
        return a 
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

时间复杂度：O(n)，因为进行了数次同步的遍历操作，每次遍历的元素不超过 n，所以时间复杂度为 O(n)。
空间复杂度：O(n)，因为借助了两个长度不超过 n 的数组辅助计算，所以空间复杂度为 O(n)。

方案二：纵向计算，利用单调递减栈，每一次出栈都意味着会接到雨水（但可能会出现没接住的情况）。

// rect 矩形。
type rect struct {
    height int
    width  int
}

func trap(height []int) int {
    ans := 0
    // 单调递减栈
    // 在构建单调递减栈的过程中，每一次的出栈都表示可以接到雨水
    stk := make([]*rect, 0, len(height))
    
    for _, h := range height {
        accumulatedWidth := 0
        // 栈顶元素的高度小于当前元素，满足出栈条件
        for len(stk) > 0 && stk[len(stk) - 1].height < h {
            // 取栈顶
            top := stk[len(stk) - 1]
            accumulatedWidth += top.width
            // 将栈顶元素出栈
            stk = stk[:len(stk) - 1]
            // 如果栈中还有元素
            // 如果栈中没有元素就无法构成 凹 行，从而无法接住雨水
            if len(stk) > 0 {
                up, bottom := min(h, stk[len(stk) - 1].height), top.height
                // 累加结果
                ans += (up - bottom) * accumulatedWidth
            }
        }
    
        // +1 为累加自身宽度
        accumulatedWidth += 1
        // 入栈
        // accumulatedWidth 中包含了从出栈操作中累积的宽度
        stk = append(stk, &rect{
            height: h,
            width:  accumulatedWidth,
        })
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

时间复杂度：O(n)，因为需要遍历所有数组元素才能完成计算，每次遍历中还附带嵌套的出栈遍历操作，但均摊（每个元素最多出入栈一次）后时间复杂度仍为 O(n)。
空间复杂度：O(n)，因为使用了一个长度不超过 n 的单调栈辅助计算，所以空间复杂度为 O(n)。

力扣 42. 接雨水

CATALOG

FEATURED TAGS