乐趣区

关于go:Leetcode专题42接雨水

力扣链接:
https://leetcode.cn/problems/trapping-rain-water/description/
解题思路:
给定一个数组 height,其中 height[i] 示意第 i 个地位的高度,假如它形成的图形是一个容器,求这个容器可能接住多少雨水。代码应用双指针的形式,从数组的两端开始向两头挪动,保护右边和左边的最高柱子别离为 leftMax 和 rightMax。在挪动指针的过程中,如果右边的柱子比左边的柱子低,则阐明右边的柱子可能会挡住左边的柱子,此时计算右边的柱子可能接住多少水,并将 leftMax 更新为以后柱子的高度。如果左边的柱子比右边的柱子低,则阐明左边的柱子可能会挡住右边的柱子,此时计算左边的柱子可能接住多少水,并将 rightMax 更新为以后柱子的高度。最终返回可能接住的雨水总量

func trap(height []int) int {
    var left, right, leftMax, rightMax, res int
    right = len(height) - 1
    for left < right {if height[left] < height[right] {if height[left] >= leftMax {leftMax = height[left]  // 设置右边最高柱子
            } else {res += leftMax - height[left]  // // 左边必然有柱子挡水,所以遇到所有值小于等于 leftMax 的,全副退出水池中
            }
            left++
        } else {if height[right] > rightMax {rightMax = height[right]  // // 设置左边最高柱子
            } else {res += rightMax - height[right]  // // 右边必然有柱子挡水,所以,遇到所有值小于等于 rightMax 的,全副退出水池
            }
            right--
        }
    }
    return res
}
退出移动版