千岛湖算法 [英] Island lake algorithm

问题描述

摘要

假设你有一个多山的2-D岛。因为它是多么的雨季，在岛上的所有谷已经完全充满水，到如此地步，再加入水会导致湖泊溢出。如果溢出走进另一个湖，它也将溢出。最终，水会流过的岛屿。由于岛屿的形状，你怎么找出湖泊将形成？

Suppose you have a mountainous 2-D island. Because of how rainy it is, all valleys in the island have been filled completely with water, to the point that adding anymore water would cause the lakes to overflow. If the overflow went into another lake, it too would overflow. Eventually, the water would flow off of the island. Given the shape of the island, how do you find out what lakes would form?

详细信息

读取序列号（每个号码重presenting点的海拔高度在2-D连接图），计算并输出所有的湖泊的表面，可能形成的山谷的高度岛。

Reading a sequence of numbers (each number representing the altitude of a point in a 2-D connected graph), compute and output the altitude of the surface of all the lakes that could form in the valleys of the island.

例如输入 4 3 7 1 3 2 3 5 6 2 1 3 3 2 3 （下图），应该给输出 4 6 3 3 中的时间最多 0的复杂性（N日志N）。

For example the input 4 3 7 1 3 2 3 5 6 2 1 3 3 2 3 (pictured below) should give the output 4 6 3 3 in time complexity of at most O(n log n).

什么算法是什么样子？可它的线性复杂度来完成？

What would the algorithm look like? Can it be done in linear complexity?

下面是code我到目前为止有：

Here is the code I have so far:

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])

这code发现所有的部分湖泊，只有在最深的峡谷注水制成，但如下图所示，我可以有一个由其它湖泊组成的湖。

This code finds all the partial lakes, made by filling only in the deepest valleys with water, but as shown below I can have a lake that is composed by other lakes.

使用上述输入4 3 7 1 3 2 3 5 6 2 1 3 3 2 3 它应该打印 4 6 3 3 但我的计划产出：

With the input above 4 3 7 1 3 2 3 5 6 2 1 3 3 2 3 it should print 4 6 3 3 but my program outputs:

4 3 3 1 2 3

我如何解决我的code，使其能够找到大峡谷，比如那些有一个小高峰呢？

How do I fix my code to allow it to find the larger valleys, such as the ones that have a small peak in them?

推荐答案

O（n）的解决方案：

O(n) solution:

进入由左到右。还记得第一个高峰，找一个更高的峰值（或相同高度的），然后绘制一个湖泊之间，比记住这个更高的峰值，并重复上述过程。 然后做同样会从右到左。它的那样简单。 （code是未经测试）

Go from left to right. Remember the first peak, find a higher peak (or a same height one), then draw a lake between them, than remember this higher peak and repeat the process. Then do the same going right to left. Its as simple as that. (Code is untested)

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]

这篇关于千岛湖算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！