arrays - 数组中每个项目之前有多少个连续元素较小

Question

给定一个数组 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)解决方案很简单，两个循环，计算元素。

这是我对 0(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) 中获得。整个解决方案是 O(n) ， 正确的？考虑过使用哈希集，但无法弄清楚。考虑过使用 kadane 算法的一些修改版本，但没有成功。

我非常想了解 O(n)解决方案。我考虑过 O(n)一整天的解决方案，我真的被困住了。

我不是本地人，所以如果能帮助我更好/更容易理解这个问题，我将不胜感激。

Answer 1

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

思路如下:对于每一个i (从左 i = 0 到右 i = n - 1 )，我们维护所有索引的集合 j这样 c[j] > c[k]对于所有 j < k < i .这个集合可以存储在一个堆栈中，最低的值在顶部。当你阅读 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]