arrays - 给定一个数组，我能否在 O(n) 中找到最长的范围，其端点是范围内的最大值？

Question

对于给定的整数数组，找出比它们之间的任何元素具有更高值的 2 个点(i 和 j)之间的最大距离。

例子:

values: 0 10  8  9  6  7  4 10  0index : 0  1  2  3  4  5  6  7  8 

对于上述解的值是 i=1, j=7, 但是

• 如果索引 7 的值为 9 而不是 10，则解为 i=3，j=7
• 如果索引 7 的值为 7 而不是 10，则解为 i=5，j=7

我在 O(n) 中看不到解决方案......有人吗？

Answer 1

一个简单的基于堆栈的解决方案。从左到右遍历数组，堆栈保存元素(技术上是索引，但使用值进行比较)是:

1. 从左边开始最大的(即数组开头和元素之间没有更大或相等的元素)
2. 堆栈中自上一个元素以来的最大元素。

在处理下一个元素x时，弹出小于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