python - 懒惰飞扬的鸟可以存活的最长时间 - 2 个阵列之间的连续间隙

Question

给定两个数组:

import numpy as np
L1 = np.array([3, 1, 4, 2, 3, 1])
L2 = np.array([4, 8, 9, 5, 6, 7])

我想有效地找到存在的最长连续间隙。

例如，设i 是两个数组的第i 个索引。

    i = 0:  elements = (3,4) -> gap in range 3-4 -> longest path = 1
    i = 1: elements = (1,8)  -> 3-4 intersect 1-8 is 3-4 -> longest path = 2
    i = 2: elements = (4, 9) -> 3-4 intersect 4-9 is NULL -> longest path = 2

    ##this is what slows my approach down
    #now, we must return to i = 1

    i = 1: elements = (1,8) -> candidate interval is 1-8 -> path = 1, longest path = 2
    i = 2: elements = (4,9) -> 1-8 intersect 4-9 is 4-8 -> path = 2, longest path = 2
    i = 3: element = (2,5) -> 4-8 intersect 2-5 is 4-5 -> path = 3, longest path = 3
    ...

如果你试着想象一下，它有点像flappy bird游戏，所以我要找的是这只鸟能保持在同一水平面而不死的最长时间

我想要一种不回溯的方法，这样我只遍历每个 i 一次。有什么建议么？最好在 python 中

更新

我写了一些代码来可视化问题(注意我在这里假设最大行数是 10，但情况并非总是如此:

def get_flappy_matrix(ceiling, floor):
    '''
    given ceiling and floor heights
    returns matrix of 1s and 0s
    representing the tunnel
    '''
    ceil_heights = np.array(ceiling)
    floor_heights = np.array(floor)
    nmb_cols = len(ceil_heights)
    flappy_m = np.ones(shape=(10, nmb_cols), dtype=np.int)

    for col in range(nmb_cols):
        for row in range(ceil_heights[col], floor_heights[col]):
            flappy_m[row, col] = 0

    return flappy_m

N = 6
L1 = np.array([3, 1, 4, 2, 3, 1])
L2 = np.array([4, 8, 9, 5, 6, 7])


m = get_flappy_matrix(L1, L2)

plt.pcolor(m, cmap=plt.cm.OrRd)
plt.yticks(np.arange(0, 10, 1), range(0, 11))
plt.xticks(np.arange(0, N+1),range(0,N+1))
plt.title(str(max_zero_len))
plt.gca().invert_yaxis()
plt.gca().set_aspect('equal')
plt.show()

现在，来自另一个 answer ，这是解决问题的一种方法(对于大输入仍然很慢):

max_zero_len = max(sum(1 for z in g if z == 0) for l in m for k, g in itertools.groupby(l))
print(max_zero_len)
 # 5

Answer 1

保留鸟可以飞过的连续孔的窗口。一次在右侧扩展一个孔，并在必要时使用以下策略从左侧移除孔​​。当您到达终点时，您设法构建的最长窗口就是解决方案。

跟踪窗口中最低的上墙，跟踪该墙之后的最低上墙，以及该墙之后的最低上墙，直到窗口中的最后一堵上墙。对下壁做类似的事情。例如，如果窗口从此处的孔 3 到孔 9:

    | | | | | | | | upper wall sections
    | | | | | | |
    |   |   |   |
    |   |   |
    |   |   |
... | ------------- window
    | -------------
    |   |
      | | | |     |
    | | | | |   | | lower wall sections
    2 3 4 5 6 7 8 9
    wall numbers

那么上界墙是 6、8 和 9，下界墙是 4 和 9。(我们通过选择右边的墙来打破平局。)

假设我们将窗口扩展到第十个洞，第十个洞看起来像这样:

    | | | | | | | | |upper wall sections
    | | | | | | |   |
    |   |   |   |   |
    |   |   |       |
    |   |   |
... | --------------- window
    | ---------------
    |   |
      | | | |     |
    | | | | |   | | | lower wall sections
    2 3 4 5 6 7 8 9 10
    wall numbers

上壁 10 低于上壁 9 和 8，因此 9 和 8 不再是上限。上限现在是 6 和 10，下限现在是 4、9 和 10。

另一方面，如果第 10 洞看起来像这样:

    | | | | | | | | | upper wall sections
    | | | | | | |
    |   |   |   |
    |   |   |
    |   |   |       |
... |               |
    |               |
    |   |           |
      | | | |     | |
    | | | | |   | | |
    2 3 4 5 6 7 8 9 10
    wall numbers

下墙 10 高于最低上界，因此我们需要移除窗口左侧的墙。我们将窗口从第 7 洞开始，移除旧的最低上限(墙 6)之前的所有内容，我们发现下一个上限，即墙 8，足够高以产生有效窗口:

    | | | | | | | | | upper wall sections
    | | | | | | |
    |   |   |   |
    |   |   | ------- window
    |   |   |       |
... |               |
    |               |
    |   |           |
      | | | |     | |
    | | | | |   | | |
    2 3 4 5 6 7 8 9 10
    wall numbers

如果上壁 8 仍然太低，我们会提前窗口从孔 9 开始，依此类推。