algorithm - 查找第k个空组的最早时间

Question

最近在面试中被问到这个问题，我仍然想不出解决办法。

一条河有N个槽位。给出一个数组 P，其中每个索引表示该位置的石头出现的时间。我必须想出一种算法来找到最早出现 K 个连续 空槽位 的时间。对于 E.G.

N = 5

P = [2,5,1,4,3]

K = 2

Initially: [0,0,0,0,0] 

All the slots are empty.

Now at:

Time t = 1, second stone will appear --> [0,1,0,0,0]

Time t = 2, fifth stone will appear --> [0,1,**0,0**,1]

Time t = 3, first stone will appear --> [1,1,0,0,1]

Time t = 4, fourth stone will appear --> [1,1,0,1,1]

Time t = 5, third stone will appear --> [1,1,1,1,1]

所以上述情况的答案是2，因为在时间2有(k = 2)个连续的空槽。

Answer 1

每次你添加一 block 石头时，你基本上将一系列连续的空槽(零)分成两部分。您可以使用这个想法来构造一棵二叉树，其中每个节点代表一个区间(0 和 1 - 石头和空白)，每个叶节点代表一个只有 0.

要添加一 block 石头，您需要找到合适的叶节点(相应的间隔必须包括您的新石头的位置)并添加新的叶节点 - 对于左侧和右侧的间隔与您添加的石头。此时您可以检查这些新间隔的长度，如果找到所需长度则停止。

这里唯一的问题是树可能会变得不平衡，因此要获得 O(nlogn) 最坏情况，您应该在树生长时应用一些技术来平衡树 - 红黑树或类似的东西 - https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree