列表可以按左侧的每个元素都小于右侧的每个元素的方式拆分多少次？

Question

例如，如果列表为：[2,1,2,5,7,6,9]，则有 3 种可能的拆分方式：
[2,1,2] [5,7,6,9]
[2,1, 2,5] [7,6,9]
[2,1,2,5,7,6] [9]

我应该计算列表可以以左侧的每个元素都小于右侧的每个元素的方式分割多少次。因此，使用此列表，输出将为 3。
这是我当前的解决方案：

def count(t):
    c= 0
    for i in range(len(t)):
        try:
            if max(t[:i]) < min(t[i:]):
                c+=1
        except:
            continue

    return c

上面的代码做了正确的事情，但它的时间复杂度不是 O(n)。我怎样才能达到相同的结果，但速度更快？

Answer 1

在线性时间内计算所有前缀最大值和后缀最小值。并在线性时间内将它们组合起来。

\n

from itertools import accumulate as acc\nfrom operator import lt\n\ndef count(t):\n    return sum(map(lt,\n                   acc(t, max),\n                   [*acc(t[:0:-1], min)][::-1]))\n

\n

雅克要求一个基准：

\n

1444.6 ms  Jacques_Gaudin\n   5.0 ms  Kelly_Bundy\n1424.5 ms  Jacques_Gaudin\n   4.4 ms  Kelly_Bundy\n1418.2 ms  Jacques_Gaudin\n   4.7 ms  Kelly_Bundy\n

\n

代码（在线尝试！）：

\n

from timeit import timeit\nfrom itertools import accumulate as acc\nfrom operator import lt\n\ndef Kelly_Bundy(t):\n    return sum(map(lt,\n                   acc(t, max),\n                   [*acc(t[:0:-1], min)][::-1]))\n\ndef Jacques_Gaudin(t):\n    if not t: return 0\n\n    v, left_max = list(t), max(t)\n    c, right_min = 0, left_max\n    while (item := v.pop()) and v:\n        if item == left_max:\n            left_max = max(v)\n        if item < right_min:\n            right_min = item\n        if left_max < right_min:\n            c += 1\n    return c\n\nfuncs = [\n    Jacques_Gaudin,\n    Kelly_Bundy,\n]\n\nt = list(range(12345))\nfor func in funcs * 3:\n  time = timeit(lambda: func(t), number=1)\n  print(\'%6.1f ms \' % (time * 1e3), func.__name__)\n

\n

Answer 2

这是我的最终答案：

def count(t):
    c = 0
    maxx = max(t)
    right = [0]*len(t)
    left = [0]*len(t)
    maxx = t[0]
   
    for i in range(0, len(t)):
    
        if maxx >= t[i]:
            left[i] = maxx
            
        if maxx < t[i]:
            maxx = t[i]
            left[i] = maxx
             
    minn = t[-1] 
    for i in range(len(t)-1,-1,-1):
        if minn <= t[i]:
            right[i] = minn
            
        if minn > t[i]:
            minn = t[i]
            right[i] = minn
           
    for i in range(0, len(t)-1):
        if left[i] < right[i+1] :
            c += 1
 
    return c