小编Rus*_*dru的帖子

给定一个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) …