对于给定的整数数组,查找具有较高值的两点(i和j)之间的最大距离而不是他们之间的任何元素
例如:
数值:0 10 8 9 6 7 4 10 0 索引:012345678
对于上述值,解为i=1,j=7,但
- 如果指数7的值为9而不是10,则解为i=3,j=7
- 如果指数7的值为7而不是10,则解为i=5,j=7
我看不到O(n)中的解决方案。。。有人吗
一个简单的基于堆栈的解决方案。从左到右遍历数组,堆栈包含以下元素之一(从技术上讲是索引,但使用值进行比较):
- 从左侧开始的最大值(即数组开始和元素之间没有较大或相等的元素)
- 自堆栈上的上一个元素以来的最大值
在处理下一个元素x
时,弹出小于x
的元素,只要它们来自类别2。然后按堆栈上的x
。显然,您需要保持当前最大值,以便能够在恒定时间内区分类别2和类别1
上面的处理是O(n)-每个元素最多只能推一次,最多只能弹出一次。有了最后一个堆栈,只需检查相邻的对(在堆栈上)——其中一对就是解决方案。这也是O(n)
下面是一张图片,上面显示了在整个阵列扫描之后,堆栈上应该保留的内容(胖矩形):
(上图中有一个小错误:左边的第四条应该比第一条粗或短,对不起)
工作原理:最后一个堆栈包含输入数组中不在任何两个较大元素之间的所有元素(我跳过了两个相等元素之间的元素)。解决方案显然是一对相邻的此类元素
下面是Python的一个实现:
从集合导入名为tuple的
E=命名的整数('E','i x')
def最大范围(iterable):
堆栈=[E(0,无)]*2#推送哨兵值
maxsofar=无
top=lambda:stack[-1]#查看堆栈上的顶部元素
对于枚举中的i,x(iterable):
而top().x<;x和顶部();maxsofar:
stack.pop()
stack.append(E(i,x))#push
maxsofar=max(maxsofar,x)
返回最大值(a的b.i-a.i,zip中的b(堆栈,堆栈[1:]))
例如:
>&燃气轮机&燃气轮机;最大范围([2,1,3])
2.