题目:接雨水

题目描述

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

0 <= n <= 3 * 104

0 <= height[i] <= 105

思路

单词注释： height[left] left位置上的格子的数量 maxl 左边格子最大的格子

这题比较难，用双指针方法代码比较简洁，用示例1举例子，先找height[left]与height[right]中小的数字，然后执行小数字方代码，如果height[left]比maxl还要大,就把maxl=height[left]，如果不是，那就说明这一格肯定可以装水（可以看代码的第一个注释的解释），把所有可以装水的格子的装水量加起来就是答案。

代码

func trap(height []int) int {
    left,right,maxl,maxr,res := 0,len(height)-1,0,0,0
    for left<=right{
         if height[left]<height[right]{
             if maxl<=height[left]{
                maxl=height[left]
             }else{
                 //左边肯定有比height[left]高的墙，右边有maxr＞maxl，右边肯定有比height[left]高的墙，水在这一格的高度就是maxl-height[left]，下面同理
                res = res+maxl-height[left]
             }
             left++
         }else{
             if maxr<height[right]{
                 maxr=height[right]
             }else{
                 //右边肯定有比height[right]高的墙
                res = res+maxr-height[right];
             }
             right--
         }
    }
    return res
}

代码效率：

执行用时：4 ms, 在所有 Go 提交中击败了74.89%的用户
内存消耗：2.8 MB, 在所有 Go 提交中击败了81.87%的用户

// 单调栈解法
func trap(height []int) int {
    var stack []int
    var res int
    for i,h := range height{
        for len(stack)>0 && height[stack[len(stack)-1]] < h{
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if len(stack) == 0{
                continue 
            }
            left := stack[len(stack)-1]
            width := i-left-1
            height := min(h, height[left]) - height[top]
            res += width*height
        }
        stack = append(stack, i)
    }
    return res
}

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

<p class="note note-primary"; style="font-size:22px">
   执行用时：8 ms, 在所有 Go 提交中击败了67.12%的用户<br>
   内存消耗：4.9 MB, 在所有 Go 提交中击败了31.09%的用户
</p>