在数组中的每个项目之前有多少个连续元素

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),对吗？考虑使用hashset,但无法弄明白.想过使用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]