每个数组项前有几个连续元素比它小？

Question

每个数组项前有几个连续元素比它小？

7

给定一个元素数量小于N < 10 000的数组，对于数组中的每个位置i，以最有效的方式查找从其左边开始（即从位置i-1到0）连续的多少个元素小于或等于array[i]。

以下是一个示例：

Array: 4 3 6 1 1 2 8 5 9
Res:   0 0 2 0 1 2 6 0 8
( pos 0 (element 4) -> 0 consecutive elements before it,
  pos 1 (element 3) -> 0 consecutive elements before it smaller than 3 (4>3)
  pos 2 (element 6) -> 2 consecutive elements before it smaller than 6 (4,3)
  and so on..
)

我认为这是一个动态规划问题，因为在问题中说了“最有效的方法”，而在解决方案中又提到了O(n)的解法。 O(n^2)的解法很简单，使用两个循环来计数元素。

以下是我对O(n)解法的思考。我们可以假设：

for (int i = 1; i < array.Length; i++) {
   if (array[i-1] > array[i])
   {
      c [i] = 0;
   }
   else {
      c [i] = c [i - 1] + MAGIC_FORMULA;
   }
}

显然，如果我发现一个元素大于下一个元素，结果显然为0（左边没有比它更小的数）。但是，先前的结果告诉我什么，以便我可以使用动态规划？我找不到那种情况的递归。此外，整个解决方案的公式必须在O(1)的时间内获得，对吗？考虑使用哈希集，但无法想出来。考虑使用一些修改版的kadane算法，但也没有成功。

我渴望了解O(n)的解决方案。我整天都在思考O(n)的解决方案，但我真的卡住了。

由于我不是本地人，因此非常感谢任何帮助使这个问题更好/更易理解的帮助。

- Rustin Alexandru

3个回答

1

显然，在原问题发布5年后，我在为我的算法课程做准备时发现了这个问题。直到今天，这仍然是我在互联网上找到的唯一解决方案。我花了相当长的时间编写这个解决方案，所以我在这里发布它。也许以后会有人需要。我的代码是用Python3编写的，并且已经尽我所能进行了重构。

from collections import  deque

def less_then_count(arr):
    stack = deque()
    ans = [0] * len(arr)    

    for i in range(len(arr)):
        while len(stack)>0 and arr[i] >= arr[stack[-1]]:
            stack.pop()
        ans[i] = i
        if len(stack) > 0:
            ans[i] -= stack[-1]+1
        stack.append(i)

    return ans


print(*less_then_count([1,2,4,2,5]))
print(*less_then_count([4, 3, 6, 1, 1, 2, 8, 5, 9]))

- Đumić Branislav

0

（编辑/管理员请在删除此评论之前阅读我对所选答案的最后一条评论。）

栈操作

在我们第一个聚合分析的示例中，我们分析了已增加新操作的堆栈。第10.1节介绍了两个基本的堆栈操作，每个操作都需要O（1）时间：

PUSH（S，x）将对象x推入堆栈S。

POP（S）弹出堆栈S的顶部并返回弹出的对象。

由于这些操作中的每一个都在O（1）时间内运行，因此让我们认为每个操作的成本为1。因此，n个PUSH和POP操作的总成本为n，n个操作的实际运行时间为（n）。

现在我们添加了堆栈操作MULTIPOP（S，k），它删除堆栈S的前k个对象，或者如果堆栈包含少于k个对象，则弹出整个堆栈。在以下伪代码中，操作STACK-EMPTY如果当前堆栈上没有对象，则返回TRUE，否则返回FALSE。

MULTIPOP(S, k) 在一个包含 s 个对象的栈上的运行时间是多少？实际运行时间与实际执行的 POP 操作数量成线性关系，因此只需根据每个 PUSH 和 POP 的抽象成本进行 MULTIPOP 分析即可。while 循环的迭代次数是弹出堆栈的对象数 min(s,k)。对于循环的每次迭代，在第二行会调用一次 POP。因此，MULTIPOP 的总成本为 min(s, k)，实际运行时间是这个成本的线性函数。

让我们分析在初始为空的堆栈上执行 n 个 PUSH、POP 和 MULTIPOP 操作的序列。该序列中 MULTIPOP 操作的最坏情况成本为 O(n)，因为堆栈大小最多为 n。因此，任何堆栈操作的最坏时间为 O(n)，因此 n 个操作的序列成本为 O(n2)，因为我们可能有 O(n) 个 MULTIPOP 操作，每个操作成本为 O(n)。虽然这种分析是正确的，但是通过单独考虑每个操作的最坏情况成本得到的 O(n2) 结果并不紧密。

通过聚合分析，我们可以获得一个更好的上界，考虑到n个操作的整个序列。实际上，尽管单个MULTIPOP操作可能很昂贵，但在最初为空的堆栈上进行任何n个PUSH、POP和MULTIPOP操作的任何序列最多只能花费O(n)。为什么？每个对象最多可以被弹出一次，每次被推入时。因此，在非空堆栈上调用POP的次数（包括MULTIPOP内部的调用）最多是PUSH操作的次数，最多为n。对于任何值n，任何n个PUSH、POP和MULTIPOP操作的序列总共需要O(n)的时间。每个操作的平均成本为O(n)/n=O(1)。在聚合分析中，我们将每个操作的摊销成本分配为平均成本。因此，在这个例子中，所有三个堆栈操作的摊销成本都是O(1)。

- Rustin Alexandru

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- md5 · Accepted Answer

有一种线性解决方案，但它并不使用动态规划，而是使用简单的循环和堆栈。首先你可以做出以下观察：计算“小于或等于c[i]的连续元素数量”几乎与找到“最大索引j <= i，使得c[j] > c[i]”是相同的任务。

思路如下：对于每个i（从左到右扫描i = 0到i = n - 1），我们维护所有索引j的集合，使得对于所有j < k < i，都有c[j] > c[k]。这个集合可以存储在一个堆栈中，最小值在顶部。当你读取c[i]时，你弹出元素，直到你得到一个索引j，使得c[j] > c[i]。这就是所需的索引。然后你可以将i推入堆栈。

例如：s是堆栈。这里ans[i]将是max{j <= i | c[j] > c[i]}。ans[i]如果前一个集合为空，则为-1。

i    0 1 2 3 4 5 6 7 8
c[i] 4 3 6 1 1 2 8 5 9
------------------------
i = 0:
    - s = []:     ans[0] = -1
    - push i:     s = [0]
i = 1:
    - s = [0]:    c[1] < c[0] -> ans[1] = 1
    - push i:     s = [0, 1]
i = 2:
    - s = [0, 1]: c[2] >= c[1] -> pop
      s = [0]:    c[2] >= c[0] -> pop
      s = []:     ans[2] = -1
    - push i:     s = [2]
i = 3:
    - s = [2]:    c[3] < c[2] -> ans[3] = 2
    - push i:     s = [2, 3]
i = 4:
    - s = [2, 3]: c[4] >= c[3] -> pop
      s = [2]:    c[4] < c[2] -> ans[4] = 2
    - push i:     s = [2, 4]
i = 5
    - s = [2, 4]: c[5] >= c[3] -> pop
      s = [2]:    c[5] < c[2] -> ans[5] = 2
    - push i:     s = [2, 5]
i = 6
    - s = [2, 5]: c[6] >= c[5] -> pop    
      s = [2]:    c[6] >= c[2] -> pop
      s = [] ->   ans[6] = -1
    - push i:     s = [6]
i = 7
    - s = [6]:    c[7] < c[6] -> ans[7] = 6
    - push i:     s = [6, 7]
i = 8
    - s = [6, 7]: c[8] >= c[7] -> pop
      s = [6]:    c[8] >= c[6] -> pop
      s = [] ->   ans[8] = -1
    - push i:     s = [8]