给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水.
预热1
木板组成水桶装水,定义高度为一数组,间隔为1,求水桶最大容量如[151263]为15,解题思路:自两边木板向中间遍历求容量,每次相对短的木板向内移动,共比较n-2次.
解析1
将水灌满,求灌满后的高度,其实就是从最高点向左右两个方向向中间遍历,依次求经过的最大值,这样一来就是从最高点向两侧递减的,再减去柱子原高度即可.
容易理解的想法还有按高度分层计算,但是时间复杂度过高.
进阶1
拓展到二维数组,这一题的解法会变得异常困难: