https://leetcode-cn.com/problems/trapping-rain-water/
可以将能填入水的地方看成一个一个的水槽，算法的作用就是确定所有水槽的边界，并找出该水槽中能盛入多少水。
最先能想到的是双指针法，就是使用两个指针，一个指向水槽开头，一个指向结尾，从左向右，先确定下水槽开头，再依次寻找水槽末尾，找到某个水槽之后再将开头的指针移向结尾，寻找下一个水槽。
观察发现，一个比较一般的规律就是如果height[end]>=height[start]，那么就说明找到了一个水槽。
但是写完以后发现很多 case 无法通过。原因是如果某一个 start 之后的所有 end 的高度都小于 start，那么我们将无法获知该 start 之后还有多少水槽。思来想去，我认为一旦出现上面的情况，就说明 start 是最高的高度，出问题的原因在于它后面没有另外一个可以和它高度匹配的水槽。如果可以按照前面的规律从后向前反向计算一次，就可以跳过这个水槽的隔阂了。
算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| func trap(height []int) int {
if len(height)<=2 {
return 0
}
start:=0
for height[start]==0 {
start++
}
total:=0
temp:=0
for end:=start+1;end<len(height);end++ {
if height[end]<height[start] {
temp+=height[start]-height[end]
}else{
total+=temp
temp=0
start=end
}
}
if l:=len(height);start<l-1 {
stop:=start
start:=l-1
for start>stop && height[start]<height[start-1] {
start--
}
temp:=0
for end:=start-1;end>=stop;end-- {
if height[end]<height[start] {
temp+=height[start]-height[end]
}else{
total+=temp
temp=0
start=end
}
}
}
return total
}
|
现在看一下 Solution 中的解法。
第一种是暴力解法：一个水槽中能盛水的量等于它左边最高的高度和右边最高的高度中比较小的那个减去它本身的高度，即min(height[leftMax],height[rightMax])-height[i]。
所以，可以通过通过暴力搜索进行求解，它的时间复杂度达到了 O(n^2)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| func trap(height []int) int {
if len(height)<=2 {
return 0
}
total:=0
for i:=1;i<len(height)-1;i++ {
maxL,maxR:=0,0
for j:=i;j>=0;j-- {
if t:=height[j];t>maxL {
maxL=t
}
}
for j:=i;j<len(height);j++ {
if t:=height[j];t>maxR {
maxR=t
}
}
t:=maxL
if maxR<maxL {
t=maxR
}
total+=t-height[i]
}
return total
}
|
可以看出，在上一种方法中计算左侧最大值和右侧最大值的循环进行了很多次的重复计算，所以如果可以使用 DP 算法 —— 用一个数组来记录这些值，就可以使用空间换时间，减少一部分的时间复杂度。
下面算法中的空间复杂度和时间复杂度都是 O(n)。第一个循环中先计算了左边和右边最大值的列表，第二个循环直接使用第一个循环中的列表进行求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| func trap(height []int) int {
l:=len(height)
if l<=2 {
return 0
}
total:=0
maxL:=make([]int,l)
maxR:=make([]int,l)
maxL[0]=height[0]
maxR[l-1]=height[l-1]
for i:=1;i<l;i++{
if maxL[i-1]>height[i] {
maxL[i]=maxL[i-1]
}else{
maxL[i]=height[i]
}
j:=l-1-i
if maxR[j+1]>height[j] {
maxR[j]=maxR[j+1]
}else{
maxR[j]=height[j]
}
}
for i:=1;i<l-1;i++ {
t:=maxL[i]
if maxL[i]>maxR[i] {
t=maxR[i]
}
total+=t-height[i]
}
return total
}
|
第三种方法是使用堆栈。这个方法也很特别，使用栈代替了上一种方法的数组来记录一个水槽的左右两边墙的高度。这个算法比较有意思，在某种程度上来说，它是“分层” 计算的。如果遇到大水槽嵌套小水槽的情况，那么它将先计算小水槽中的水量，再计算大水槽中的水量。
在当前高度比栈顶高度低的时候将当前高度入栈，在当前高度比栈顶高度高的时候，将栈顶元素出栈，记为a，a就是小容器的底部，而出栈后的栈顶元素和当前元素就是容器的两条侧边，比较两个侧边和底部的高度，取比较低的那个，然后计算它和a的高度差，接着计算两条侧边之间的距离，相乘即为能容纳的量。比较有意思的，这里的容纳量只是以a为底部时候的，而a之前入栈的元素中可能还有比a更低的，所以这就需要用一个循环继续和当前元素去比较了。
具体可以参考https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
这个算法的时间和空间复杂度都是 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| func trap(height []int) int {
total:=0
current:=0
stack:=make([]int,0)
for current<len(height) {
for len(stack)>0 && height[current]>height[stack[len(stack)-1]] {
now:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
if len(stack)==0 {
break
}
length:=current-stack[len(stack)-1]-1
h:=-height[now]
if height[current]>height[stack[len(stack)-1]] {
h+=height[stack[len(stack)-1]]
}else{
h+=height[current]
}
total+=length*h
}
stack=append(stack,current)
current++
}
return total
}
|
Solution 中的最后一个方法是双指针法。这个方法和我最开始用的有很大区别。他思考的力度比强了很多。我最开始使用的是先从左到右寻找，再从右向左寻找，其分界点是最高的那一个 bar。
但是在这个算法中，它直接将两个指针放置在数组左右两边。因为要找到能盛水的数量，不是必须知道全局情况。只知道局部情况已经可以搞定——在循环内部，首先判断是左边大还是右边大，如果左边小，那么影响水槽深度的一定是左边，所以进行左边的统计，否则进行右边的统计。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func trap(height []int) int {
total:=0
left,right:=0,len(height)-1
lMax,rMax:=0,0
for left<right {
if height[left]<height[right] {
if height[left]>=lMax {
lMax=height[left]
}else{
total+=lMax-height[left]
}
left++
}else{
if height[right]>=rMax {
rMax=height[right]
}else{
total+=rMax-height[right]
}
right--
}
}
return total
}
|