algorithm - 数组所有可能子数组的最大值

Question

如何查找/存储长度为 n 的数组的所有可能非空子数组的最大值/最小值？

如果确实查询到线段树，我生成了数组的线段树和每个可能的子数组，但效率不高。我如何在 O(n) 中做到这一点？

P.S n <= 10 ^7

For eg. arr[]= { 1, 2, 3 };  // the array need not to be sorted

sub-array     min      max
{1}            1        1
{2}            2        2
{3}            3        3
{1,2}          1        2
{2,3}          2        3
{1,2,3}        1        3

Answer 1

我认为不可能在 O(n) 中存储所有这些值。但是很容易在 O(n) 中创建一个结构，该结构可以在 O(1) 中回答查询“A[i] 是最大元素的地方有多少个子集”。

原始版本:

考虑一下朴素的策略:要知道某些 A[i] 有多少这样的子集，您可以使用一个简单的 O(n) 算法来计算数组左侧和右侧有多少个元素小于 A[i]。比方说:

A = [... 10 1 1 1 5 1 1 10 ...]

这个 5 向上有 3 个元素在左边，右边有 2 个元素小于它。由此我们知道有 4*3=12 个子数组，其中 5 是最大值。 4*3 因为左边有 0..3 子数组，右边有 0..2。

优化版:

这个简单版本的检查会对每个元素进行 O(n) 次操作，所以毕竟是 O(n^2) 次。如果我们可以在 O(n) 中一次计算出所有这些长度，那不是很好吗？

幸运的是，有一个简单的算法。只需使用一个堆栈。正常遍历数组(从左到右)。将每个元素索引放入堆栈中。但在放置之前，删除所有值小于当前值的索引。当前索引之前的剩余索引是最近的较大元素。

要在右侧找到相同的值，只需向后遍历数组即可。

这是一个 Python 概念验证示例，展示了该算法的实际应用。我还实现了原始版本，因此我们可以交叉检查优化版本的结果:

from random import choice
from collections import defaultdict, deque

def make_bounds(A, fallback, arange, op):
    stack = deque()
    bound = [fallback] * len(A)
    for i in arange:
        while stack and op(A[stack[-1]], A[i]):
            stack.pop()
        if stack:
            bound[i] = stack[-1]
        stack.append(i)
    return bound

def optimized_version(A):
    T = zip(make_bounds(A, -1, xrange(len(A)), lambda x, y: x<=y), 
            make_bounds(A, len(A), reversed(xrange(len(A))), lambda x, y: x<y))

    answer = defaultdict(lambda: 0)
    for i, x in enumerate(A):
        left, right = T[i]
        answer[x] += (i-left) * (right-i)
    return dict(answer)

def naive_version(A):
    answer = defaultdict(lambda: 0)
    for i, x in enumerate(A):
        left = next((j for j in range(i-1, -1, -1) if A[j]>A[i]), -1)
        right = next((j for j in range(i+1, len(A)) if A[j]>=A[i]), len(A))
        answer[x] += (i-left) * (right-i)
    return dict(answer)


A = [choice(xrange(32)) for i in xrange(8)]    
MA1 = naive_version(A)
MA2 = optimized_version(A)

print 'Array:    ', A
print 'Naive:    ', MA1
print 'Optimized:', MA2
print 'OK:       ', MA1 == MA2