Q:

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路

很经典的算法题，据说字节特别喜欢考这道题🤣

这题解法很多，比较暴力的就是按行求，类似俄罗斯方块一样，求每一行能接多少雨水，但这样复杂度会很高，在leetcode中无法AC 。 我采用比较好想的动态规划思路

首先明确我们是按列求，也就是说是求每一列能装多少水，然后加起来。思考一下可以想到，对于某个位置能装多少水，其实是由 该位置 左边部分最高的柱子 和 右边部分最高的柱子 两者中取较短 的那根 它的高度就是该位置能装的水

所以可以先维护两个数组，dp1[i],dp2[i]分别表示i下标位置的左边的最大柱子高度和右边的最大柱子高度 。有了这俩数组后我们计算i位置的存水量就是 Math.min(dp1[i],dp2[i]) , 不过需要注意，这个存水量一定要大于该位置的柱子高度 即height[i]。

Code

Prev

46. 全排列

Next

17. 电话号码的字母组合