算法实践——Twitter算法面试题(积水问题)的线性时间解法【转载】

  1. 云栖社区>
  2. 博客>
  3. 正文

算法实践——Twitter算法面试题(积水问题)的线性时间解法【转载】

华山青竹 2013-12-05 11:16:00 浏览455
展开阅读全文

文章来源:http://www.cnblogs.com/grenet/p/3413809.html

 

问题描述:在下图里我们有不同高度的挡板。这个图片由一个整数数组所代表,数组中每个数是墙的高度。下图可以表示为数组(2、5、1、2、3、4、7、2)。假如开始下雨了,那么挡板之间的水坑能够装多少水(水足够多)呢?

 

Wall-1

 

 

 

下图是装满水的情况,一个蓝色格子代表一个单位的水。下图中一共装了10个单位的水。

 

Wall-2

 

 

 

 

 

问题分析:

 

 

 

先看看下图,判断哪个单元格的水能留下来。下图中的两个单元格,一个红色的单元格和一个绿色的单元格,哪个单元格的水是溜走了,哪个单元格的水能留下来?

 

Wall-3

 

很明显的,上图中的红色单元格的水会流走,绿色单元格的水会被留下来。

 

那么,仔细看看这两个单元格的区别在哪儿

 

区别就是,红色单元格只有右边的挡板比它高(不低于它),而绿色单元格左右两边都有挡板比它高(左边最高是5,右边最高是7)

 

这也就很好的理解了,如果水要能留下来,必须左右两边的挡板都比它高才行。(很明显的,不管哪一侧的挡板比水低,水就会朝哪个方向流出去)

 

 

 

于是,我给每个挡板定义了3个属性

 

V属性:本挡板的高度

 

L属性:本挡板左侧挡板的最高高度

 

R属性:本挡板右侧挡板的最高高度

 

 

 

那么,该挡板上方能积水的充要条件就是:L>V并且R>V

 

如果该挡板能积水,则积水量为:Min(L-V,R-V)

 

 

 

那么总的积水量就是所有挡板的积水量总和

 

 

 

问题就变成,如何求出每块挡板的L属性和R属性

 

用V、L、R三个数组标示挡板组的三个属性。一共有N块挡板,数组的下标从0到N-1。

 

V(i)表示第i块挡板的高度、L(i)表示第i块挡板的L属性、R(i)表示第i块挡板的R属性

 

可知的是L(0)=0,R(N-1)=0;

 

 

 

不失一般性,考虑第i块挡板的L属性(i>0)。L(i-1)表示第i-1块挡板的L属性。那么,可知

 

如果L(i-1)>V(i-1),则L(i)=L(i-1)

 

如果L(i-1)≤V(i-1),则L(i)=V(i-1)

 

综上所述:L(i)=Max(L(i-1),V(i-1))(i>0)

 

同理可述:R(i)=Max(R(i+1),V(i+1))(i<N-1)

 

 

 

而由于L(0)=0,R(N-1)=0。则说明第0、N块挡板(最左和最右的挡板)是不会积水的

 

因此,计算L和R的属性以及计算积水量的下标从1开始到N-2即可

 

 

 

代码如下:

 

Public Class clsFillWater 
    Public Shared Function FillWater2(ByVal ParamArray Nums() As IntegerAs Integer 
        Dim L(Nums.Length - 1) As Integer 
        Dim R(Nums.Length - 1) As Integer 
        Dim I As Integer 
        Dim Result As Integer = 0

 

 

 

        If Nums.Length < 3 Then Return 0

 

 

 

        L(0) = 0 
        R(Nums.Length - 1) = 0

 

        For I = 1 To Nums.Length - 2 
            L(I) = Math.Max(L(I - 1), Nums(I - 1)) 
            R(Nums.Length - 1 - I) = Math.Max(R(Nums.Length - I), Nums(Nums.Length - I)) 
        Next

 

 

 

        For I = 1 To Nums.Length - 2 
            If L(I) > Nums(I) AndAlso R(I) > Nums(I) Then 
                Result += Math.Min(L(I), R(I)) - Nums(I) 
            End If 
        Next

 

        Return Result 
    End Function 
End Class

 

 

 

从代码看,该算法的时间效率是O(N)的,是线性时间的。在文章 Twitter算法面试题详解(Java实现) 的评论中也有一个线性时间的算法(效率相当,可能还优于本算法),不过理解上不如这个简单明了。

 

作者:万仓一黍
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

 

 

网友评论

登录后评论
0/500
评论
华山青竹
+ 关注