将列表中的每个元素与所有先前的连续元素进行比较

Question

我想将列表 a 的每个元素与其前面的连续元素进行比较。 i 在前向方向的每次迭代都需要 i 在后向方向的 j 迭代次数（或者简单地从 i 的当前索引反向迭代 j）并比较先前的连续元素是否满足条件 a[i] >= a[j] .如果条件为真，则计数增加 1 (count++) 如果条件失败（即 a[i] < a[j] 在任何索引处）将计数附加到新列表 li[] 并打印 li.

我尝试了以下方法但失败了：

a = [1,2,3,2,4,6,1,2]
li=[]
count = 0
for i in range(len(a)):
  for j in range(i,0,-1):
    while a[i] >= a[j]:
      count+=1
    li.append(count)
    print(li)

输出应如下所示：

1 2 3 1 5 6 1 2

有什么具体的方法可以解决这个复杂度为 O(n) 的问题。比如有没有什么算法可以解决某个方法中需要2个或多个嵌套循环的问题，优化时间复杂度。

Answer 1

这是需要堆栈在线性时间内解决的前瞻或后视问题类别：

def smaller_preceding(a):
    stack = []
    result = []
    for i, x in enumerate(a):
        while stack and a[stack[-1]] < x:
            stack.pop()
        # current index minus index of last bigger element!
        result.append(i - (stack[-1] if stack else -1))
        stack.append(i)  
    return result

>>> smaller_preceding([1,2,3,2,4,6,1,2])
[1, 2, 3, 1, 5, 6, 1, 2]

堆栈跟踪严格递减元素的索引，例如在某一时刻它将是：

[2, 3]  
# stack contains indeces  (0 and 1 have been popped)

对应元素：

[3, 2]  
# ... of decreasing elements (... because 1 and 2 were smaller than 3)

原因是对于 a 中的每个元素 x，你知道你可以完全忘记所有更小的先前元素，因为你永远不会“过去”x稍后回顾（如果任何更小的元素小于未来的元素，那么 x！）。

您可以轻松验证 for 循环有 n 次迭代。此外，可以看到 while 循环也最多有 n 次迭代（即使它是嵌套的），因为每个索引只能从堆栈中弹出一次。因此，整个算法在时间上是线性的 space.

Answer 2

您可以使用 numpy 评估整体的比较 np.array。这为您节省了一个循环。第一步创建包含数字大于当前值的所有索引的数组：array([1, 2, 3, 4, 5]（对于原始列表的索引 6）。
在第二步中，将空数组添加到 li 作为当前索引 +1 idx+1 因为这是该点必须返回的距离（直到列表的开头）。如果数组非空，将添加 idx 和最大值（index 数组中最右边的索引）之间的差值。同样，这是指针必须移动的距离。

import numpy as np

a = np.array([1, 2, 3, 2, 4, 6, 1, 2])
li = []

for idx, val in enumerate(a):
    index = np.where(a[0:idx+1] > val)
    if np.size(index) == 0:
        li.append(idx+1)
    else:
        li.append(idx - np.max(index))
    
print(li)

将列表中的每个元素与所有先前的连续元素进行比较

Compare each element in a list with all the previous consecutive elements

python

algorithm

nested-loops