列表可以拆分多少次，使左边的每个元素都小于右边的每个元素

Question

例如，如果列表为：[2,1,2,5,7,6,9]，则有三种可能的拆分方式：
[2,1,2][5,7,6,9]
[1,2,5][7,6,9]
[2,2,5,7,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

代码(在线试用！(：

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

我的答案与kelly的答案非常相似——我们都计算有效分割点的最小值和最大值，然后检查每次分割的条件。

我的速度比凯利的慢+50%左右，因为它没有像凯利的那样完全发挥作用。

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参数，请尝试count==swap(：

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

Answer 3

我的尝试：

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

非常简单，只有在可能不同的情况下才计算最大值/最小值。

Answer 4

这是我的最终答案：

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