接雨水,二哥的 LeetCode 刷题笔记,暴力解法,但效率很高
二哥瞎逼逼:接雨水是一道非常经典的 LeetCode 题,在不少笔试中见到过,所以大家最好都要掌握。
题意
给定 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
分析
虽然这道题是 hard,但不要怕,我们可以抽丝剥茧将重要的信息剥离出来,一步一步解决它。
一个 能接雨水的容器 肯定是由 左边界、右边界和底边构成的。
换句话说,每一根柱子 i 用来做为底边的时候,它能接多少雨水,取决于左边界和右边界的最小值。

1 条评论
回复