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

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

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

from itertools import accumulate as acc
from operator import lt

def count(t):
    return sum(map(lt,
                   acc(t, max),
                   [*acc(t[:0:-1], min)][::-1]))

Jacques 请求了一个基准：

1444.6 ms  Jacques_Gaudin
   5.0 ms  Kelly_Bundy
1424.5 ms  Jacques_Gaudin
   4.4 ms  Kelly_Bundy
1418.2 ms  Jacques_Gaudin
   4.7 ms  Kelly_Bundy

代码（Try it online!）：

from timeit import timeit
from itertools import accumulate as acc
from operator import lt

def Kelly_Bundy(t):
    return sum(map(lt,
                   acc(t, max),
                   [*acc(t[:0:-1], min)][::-1]))

def Jacques_Gaudin(t):
    if not t: return 0

    v, left_max = list(t), max(t)
    c, right_min = 0, left_max
    while (item := v.pop()) and v:
        if item == left_max:
            left_max = max(v)
        if item < right_min:
            right_min = item
        if left_max < right_min:
            c += 1
    return c

funcs = [
    Jacques_Gaudin,
    Kelly_Bundy,
]

t = list(range(12345))
for func in funcs * 3:
  time = timeit(lambda: func(t), number=1)
  print('%6.1f ms ' % (time * 1e3), func.__name__)

Answer 2

我的尝试：

def count(t):
    max_el = t[0]
    min_el = min(t[1:])
    res = 0
    for i in range(len(t)-1):
        if t[i] == min_el:
            min_el = min(t[i+1:])
        if max_el < t[i]:
            max_el = t[i]
        if max_el < min_el:
            res +=1
    return res

非常简单，只计算 max/min 如果它可能不同。

Answer 3

这是我的最终答案：

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

Answer 4

我的回答结果与上面凯莉的答案非常相似——我们都计算有效分割点的最小值和最大值，然后检查每个分割点的条件。

我比 Kelly 的慢 50% 左右，因为它不像 Kelly 的那样功能齐全。

from itertools import accumulate as acc
from typing import List
def paddy3118(lst: List[int]) -> int:
    
    # min of RHS for any split
    min_from_r = list(acc(lst[::-1], min))[::-1]
    # max of LHS for any split
    max_from_l = list(acc(lst, max))

    # Condition for valid split
    return sum(max_from_l[split] < min_from_r[split+1]
               for split in range(len(lst) - 1))

以下函数可以生成有趣的测试数据，（尝试 count == swap 以获得更大的 count 参数：

def _gen_swap(count, swaps):
    ans = list(range(count))
    for i in range(swaps):
        s = random.randint(0, count - 2)
        ans[s], ans[s+1] = ans[s+1], ans[s]
    return ans

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

How many times can a list be split in a way that every element on the left is smaller than every element on the right?

python

algorithm

time-complexity