接雨水，二哥的 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 用来做为底边的时候，它能接多少雨水，取决于左边界和右边界的最小值。
2人已点赞
热门评论
1 条评论
回复