岛湖算法

Question

摘要

假设你有一个多山的二维岛屿.由于天气多雨,岛上的所有山谷都被水完全填满,以至于再加水会导致湖泊溢出.如果溢流进入另一个湖泊,它也会溢出.最终,水将从岛上流出.鉴于岛屿的形状,你如何找出形成的湖泊？

细节

读取一系列数字(每个数字代表二维连通图中一个点的高度),计算并输出可能在岛屿山谷形成的所有湖泊表面的高度.

例如,输入4 3 7 1 3 2 3 5 6 2 1 3 3 2 3(如下图所示)应该给出4 6 3 3最多时间复杂度的输出O(n log n).

算法会是什么样的？它可以线性复杂吗？

这是我到目前为止的代码:

import sys

def island_lakes():
    lst=[]
    lst1=[0]*3
    x=[int(i) for i in sys.stdin.readline().split()]
    lst.extend(x)

    print(lst)       


    for x in range(len(lst)-1):
        if x>0:
            lst1[0]=lst[x-1]
            lst1[1]=lst[x]
            lst1[2]=lst[x+1]
            if lst1[1]<lst1[0] and lst1[1]<lst1[2]:
                if lst1[0]>lst1[2]:
                    print(lst1[2])
                else:
                    print(lst1[0])

这段代码找到了所有的部分湖泊,只用最深的山谷填充水,但如下图所示我可以有一个由其他湖泊组成的湖泊.

使用上面的输入4 3 7 1 3 2 3 5 6 2 1 3 3 2 3它应该打印4 6 3 3但我的程序输出:

4 3 3 2 3

如何修复我的代码以允许它找到更大的山谷,例如那些山峰较小的山谷？

Answer 1

为了找到可能形成的湖泊的最大海拔高度,您需要找到所有峰值或高于其周围点的点.稍微修改一下代码,我们可以在一次迭代中轻松获得峰值:

lst = [0] + lst + [0] # Add zeros to either side to avoid having to deal with boundary issues
peaks = []
for x in range(1, len(lst)-1):
    if lst[x-1] =< lst[x] >= lst[x+1]: # "x =< y >= z" is the same as "x =< y and y >= z"
        peaks.append(lst[x])

对于你的例子4 3 7 1 3 2 3 5 6 2 1 3 3 2 3,峰值将是

[4, 7, 3, 6, 3, 3, 3]

现在,我们需要合并湖泊.我们找到哪些湖泊可以合并的方法是通过峰值列表,跟踪到目前为止的最高峰值,并且对于每个峰值,我们删除任何先前的峰值,这些峰值低于它,到目前为止最高峰值.但是,这不需要任何预见信息,因此我们可以for在与首先找到峰值的循环相同的循环中执行此操作:

highest_so_far = 0
for x in range(1, len(lst)-1):
    if lst[x-1] =< lst[x] >= lst[x+1]: # "x =< y >= z" is the same as "x =< y and y >= z"
        while peaks and highest_so_far > peaks[-1] < lst[x]:
            peaks.pop()
        if lst[x] > highest_so_far:
            highest_so_far = lst[x]
        peaks.append(lst[x])

这将减少我们示例中的峰值

[4, 7, 6, 3, 3, 3]

现在,为了找到所有湖泊,我们只需浏览列表并输出每对的下部.然而,有一个皱纹 - 3系列,我们怎么知道它是平坦的地面还是分隔相同高度的山峰的湖泊？我们必须知道这些点是否彼此相邻.这可以通过包括位置信息和每个峰值来完成 -

peaks.append((lst[x], x))

然后,当我们浏览最终的峰值列表时,我们检查两者中的较低者,如果它们相等,我们检查它们是否彼此相邻(如果它们是没有湖).

为了让我不为你编写所有代码,我将留给你修改循环以使用peaks包含元组并根据找到的峰值编写确定湖泊的循环.

至于时间复杂度,我相信这是在线性时间内运行的.显然,我们只运行一次列表,但while中间有循环.在每次迭代时,while循环将检查至少一个峰值,但如果它检查多个峰值,则是因为至少有一个峰值已被删除.因此,超过每次迭代检查一次,不会多次检查峰值,最多会给出所需时间的线性增加.

Answer 2

O(n)解决方案:

从左到右.记住第一个峰值,找到一个更高的峰值(或一个相同的高度),然后在它们之间绘制一个湖泊,而不是记住这个更高的峰值并重复该过程.然后从右到左做同样的事情.就这么简单.(代码未经测试)

def island_lakes():
    lst=[]
    x=[int(i) for i in sys.stdin.readline().split()]
    lst.extend(x)

    print(lst)       

    cur_height = lst[0]
    valley_found = false
    for i in range(1, len(lst)):
        if lst[i] >= cur_height and valley_found:
            print(cur_height)
            valley_found = false
        else:
            valley_found = true

        if lst[i] >= cur_height:
            cur_height = lst[i]

    cur_height = lst[-1]
    valley_found = false
    for i in range(len(lst)-2, -1, -1):
        if lst[i] >= cur_height and valley_found:
            print(cur_height)
            valley_found = false
        else:
            valley_found = true

        if lst[i] >= cur_height:
            cur_height = lst[i]