tem*_*def 21
我相信以下算法在O(n)时间运行并产生最佳解决方案.这有点棘手,所以我将逻辑分为两种情况,一种是我们考虑数组中没有重复值的情况,另一种是我们考虑允许重复的情况.
我们将使用的关键数据结构是笛卡尔树,它是由一系列数据构建的最大堆,其特性是树的节点的顺序遍历产生顺序的值.它们出现了.关键的细节是,可以在O(n)时间内为一系列元素构建笛卡尔树.
举个例子,给定序列4 1 0 3 2,我们得到这个笛卡尔树:
4
\
3
/ \
1 2
\
0
请注意,inorder walk确实会返回4 1 0 3 2.
我现在声称我们正在寻找的范围的端点必须是笛卡尔树中的父/子对(即,第一个节点是第二个节点的父节点,反之亦然).请注意,我们不是在寻找节点和任何祖先,而是特定的父/子对.为了证明这一点,我证明了以下两个主张:
权利要求1:笛卡尔树中的任何父/子对定义原始序列中的值范围,其不具有大于端点的任何中间值.
权利要求2:序列中没有任何大于其端点的中间值的任何值范围必须将这些端点作为笛卡尔树中的父/子对.
总之,这些共同证明我们正在寻找的范围必须是笛卡尔树中的父/子对.这为我们提供了一种简单的线性时间算法,用于在所有值都不同时解决问题.首先,在O(n)时间内,为该范围构建笛卡尔树.接下来,递归地探索树,并为每个父/子对找到这些对之间的距离,取我们找到的最大范围.第二步也在O(n)中运行,因为笛卡尔树是二叉树,因此边数是O(n).
权利要求1的证明:父母/子女对必须看起来像
u
\
v
/ \
A B
要么
u
/
v
/ \
A B
回想一下,笛卡尔树以一种方式存储其元素,即遍历树的元素产生用于按照它们在数组中出现的顺序生成树的数组的元素.这意味着在情况(1)中,我们正在查看以u开头的一系列元素,包含所有A,并以b结尾.类似地,在情况(2)中,范围以v开始,然后包含所有B,然后以u结束.我们证明了u和v之间没有任何值的说法,这些值比u或v大于矛盾.假设是这种情况,并且值w大于u或v.通过笛卡尔树的定义,如果w在原始序列中位于u和v之间,那么在情况(1)中它必须在子树A和在情况(2)中它必须在子树B中.但是笛卡尔树是最大堆,因此在情况(1)中,u和v都大于A中的所有,并且在情况(2)中你和v比B中的所有东西都大,这是一个矛盾.因此,任何父/子对之间的值范围必须不大于父对象或子对象.
权利要求2的证明:通过对立; 我们展示如果原始数组的子序列以u开头并以v结尾,其中包含的元素大于u或v,则u和v不能是笛卡尔树中的父/子或子/父对.证明实际上与上述相同 - 如果u和v是父/子对,那么在上面的情况(1)中w必须在A中并且在情况(2)中w必须在B中,在这两种情况下违反了笛卡尔树是最大堆的事实.
上面的证明告诉我们,如果所有值都是不同的,我们可以通过构建笛卡尔树并进行简单的树步行来在线性时间内解决这个问题.但是,如果允许元素重复,如在原始问题陈述中会发生什么？在这种情况下,我们可以使用修改后的笛卡尔树结构.我们将允许节点组合成具有相同值的多个不同笛卡尔树值的"元节点".例如,序列2 7 1 7 8 0 3 8 2将如下所示:
[8 ------- 8]
/ \ \
/ 3 2
/ /
/ 0
/
[7 -- 7]
/ \
2 1
这里,根是一个元节点,由两个节点组成,值为8,前8节元节点由两个7元节点组成.
出于符号目的,让metanode的"leftest"节点是metanode中最左边的节点,让metanode的"rightest"节点成为metanode中最右边的节点.
在这个修改过的笛卡尔树中,我们可以将节点的顺序定义定义为以从左到右的顺序访问元节点中的所有节点,对其包含的每个节点进行顺序遍历.然后,我们强制修改的笛卡尔树是严格的最大堆(每个节点必须严格地大于其任何子节点)并且树的顺序遍历产生的值与它们在原始序列中出现的顺序相同.
请注意,此通用构造包含我们原始解决方案作为特例 - 如果所有值都是不同的,则此树结构中没有任何不同.我还将说明没有证据表明可以通过直接修改标准笛卡尔树算法在O(n)中构建其中一个结构.
在此修改后的树结构中,一系列值没有至少与端点一样大的中间值对应于:
- 父母和其左子女的最右边的节点.
- 父母和其右孩子的最低节点.
- 同一元节点中的两个相邻节点.
前两个声明的证明几乎是对上述案例的证据的直接修改.不同之处在于,与其说违反max-heap属性的矛盾证明,相反,你会声称它违反了强大的max-heap属性.您还可以说,在范围中间的任何相等值都必须表现为节点,这些节点会阻止范围端点成为元节点中最左侧或最右侧的节点.第三种权利要求的证明(大致)两个节点之间的任何节点必须严格小于端点,如果中间有相等的值,则两个节点不会相邻的节点.
鉴于此观察,我们可以在O(n)时间内解决原始问题如下.首先,从输入范围构建一个广义笛卡尔树.接下来,遍历树并查看可能是范围的所有指示元素对,选择您找到的最大元素.因为对于每个节点,只需要检查一定数量的其他节点(其父节点,左右兄弟节点和子节点最多给出五个节点进行检查),这可以在O(n)时间内完成,以便净运行时间为上).
呼!这是一个很棒的问题.我不知道这是否是一个理想的解决方案,但它至少证明在O(n)时间内可以做到这一点.如果有人想出更好的答案,我很乐意看到它.
- 虽然有趣且在许多方面具有教育意义,但这肯定是过于人为的.Rafal Dowgird在下面给出的解决方案是一个清晰的棱镜. (5认同)
- 令人印象深刻!希望我有时间阅读所有:) (3认同)
Raf*_*ird 21
基于堆栈的简单解决方案.从左到右迭代数组,使用堆栈保持元素(技术上,索引,但使用值进行比较),它们是:
- 从左边开始最大(即数组的开头和元素之间没有更大或相等的元素)
- 自堆栈上的前一个元素以来最大的.
处理下一个元素时x,pop元素小于x它们来自上面的类别2.然后按下x堆栈.显然,您需要保持当前最大值,以便能够在恒定时间内辨别类别2和1.
上面的处理是O(n) - 每个元素最多可被推送一次并且最多弹出一次.拥有最后的堆栈,只需检查相邻的对(在堆栈上) - 其中一对是解决方案.这也是O(n).
这是一张图片,显示了整个数组扫描后应该留在堆栈(胖矩形)的内容:
(在上面的图片中有一个小错误:左边的第四个栏应该比第一个更粗或拉得更短,抱歉)
为什么会这样:最终的堆栈包含输入数组中不在任何两个较大元素之间的所有元素(我跳过了两个相等元素之间的元素的情况).解决方案显然是一对相邻的元素.
这是Python中的一个实现:
from collections import namedtuple
E = namedtuple('E', 'i x')
def maxrange(iterable):
stack = [E(0, None)]*2 # push sentinel values
maxsofar = None
top = lambda: stack[-1] # peek at the top element on the stack
for i, x in enumerate(iterable):
while top().x < x and top().x < maxsofar:
stack.pop()
stack.append(E(i, x)) # push
maxsofar = max(maxsofar, x)
return max(b.i-a.i for a,b in zip(stack, stack[1:]))
例:
>>> maxrange([2,1,3])
2
Rafals解决方案很好,但我们可以在没有堆栈的情况下完成,从而节省一些内存.这是一个简短而有效的实施方式O(n):
def highDist(seq):
res, ltr, rtl = 0, 0, 0
for i in range(len(seq)):
if seq[i] >= seq[ltr]:
res = max(res, i-ltr)
ltr = i
if seq[-i-1] >= seq[-rtl-1]:
res = max(res, i-rtl)
rtl = i
return res
运行示例输入:
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 10, 0])
6
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 9, 0])
4
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 7, 0])
2
>>> print highDist([])
0
诀窍是,如果我们有两个点,a并且b它们之间的所有东西都小于它们,那么我们搜索的最大距离是|b-a|或者完全在该范围之外.因此,如果我们以这种方式对整个序列进行分区,其中一个就是我们要搜索的范围.
我们可以轻松地使分区从每一端创建一个后果.