我最近在一次采访中被问到这个问题,我仍然无法想出解决方案.
河里有N个插槽.给出阵列P,其中每个指数表示该位置处的石头将出现的时间.我必须想出一个算法来找到K个连续空槽的最早时间.对于EG
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)连续的空槽.
每次添加一块石头时,你基本上将一系列连续的空槽(零)分成两部分.您可以使用此构思构造二叉树,其中每个节点表示一个区间(零和一个 - 石头和空格),每个叶节点仅代表一个零区间.
要添加石头,您可以找到相应的叶节点(相应的间隔必须包括新石头的位置)并添加新的叶节点 - 左侧和右侧的间隔与您添加的石头相比.此时您可以检查这些新间隔的长度,如果找到所需长度的间隔则停止.
这里唯一的问题是树可能变得不平衡所以为了得到O(nlogn)最坏的情况你应该应用一些技术来平衡树的生长 - 红黑树或类似的东西 - https://en.wikipedia.组织/维基/自balancing_binary_search_tree
终于在leetcode上找到了O(n)时间复杂度和O(n)空间复杂度的解法。简单解释一下：
想法是用一个数组
days[]来记录每个位置花的开花日期。那意味着days[i]，正是该花的盛开之日i+1。我们只需要找到一个days[left, left+1,...,left+k-1, right]满足以下条件的子数组：对于任意i = left+1,..., left+k-1，我们可以有days[left] < days[i] && days[right] < days[i]。那么，结果就是max(days[left], days[right])。
这是确切解决方案的链接：https ://discuss.leetcode.com/topic/104771/java-c-simple-on-solution