本题来自Leetcode,题目传送门:「链接」
难度:困难
编程语言:Go
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
引用自Leetcode
提示:
1. n == height.length
2. 1 <= n <=
3. 0 <= height[i] <=
要接住雨水,必须形成凹槽。
第一种思路:找到这个柱子左边最高的,和右边最高的,然后计算这个柱子能接到的雨水。量=min(左边最高,右边最高)。
这种方法下:
1. 每一个柱子都要往两边扩散计算,时间复杂度是O(n)
2. 需要两个额外的数组来保留n个柱子能接到的雨水,空间复杂度为O(n).
第二种思路:寻找比左边高的柱子。 当找到凹槽后,可累积的雨水为:超过该高度的面积。比如:
1 ~ ~ ~ 1
1 1 * 1 1
1 1 1 1 1
从第四个柱子开始,出现第一个凹槽,可累计的雨水是"*",宽为1,高为1 ,累积雨水1个单位。
第五个柱子出现第二个凹槽,其和等高的柱子(第一个柱子)的宽度"~"为3,高为1,所以累积的雨水是3个单位。
图示被丢弃的图样:
1
1 1 2
1 1 1 1 2
从第一个柱子开始,左低右高,无法形成凹槽,丢弃。第三个柱子不能丢弃,因为后面可能存在"2"构成的柱子。第四个柱子同理需要保留,但是同样不累积雨水。
这种方法下:
1. 每一个元素需要入一次栈,时间复杂度为O(n);
2. 需要一个栈来保存柱子的坐标,最坏情况下保留n个,空间复杂度为O(n);
第三种思路:由于接到的雨水由左右两个最高的高度的最小值决定,所以可以从左右两侧往中间靠拢,动态的计算左右的最大值。
其中的难点:当从左往右时,左边的最大值是可信的,但是右边的最大值 <= 右边真实的最大值。同理,从右往左也是如此。
这种情况下,如果是从左往右且左边的最大值小于右边的最大值,则该柱子接到的雨水必然等于:左边最大值-当前柱子的高度。同理从右往左,右边最大值小于左边最大值时,也是如此。
则这种情况下,按照相同方向靠拢是可靠的,如从左往右的继续向右计算下一个柱子的累积雨水情况。如果左边最大值小于右边最大值,则右边向左靠拢。
这种方法下:
1. 每一个元素需要一次遍历,时间复杂度为O(n);
2. 需要保留leftMax和rightMax,空间复杂度为O(1)。
先上测试
第一种方法比较简单,此处不实现。
第二种方法:
第三种方法:
Leetcode运算结果
方法二:
方法三: