一个列表可以被分割多少次，以便左侧的每个元素都小于右侧的每个元素？

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)的时间复杂度。我该如何获得相同的结果，但速度更快？

- Kodtld

---

如果左边有4个元素，并且它们都比右边的元素小，那么添加一个新元素不需要计算所有5个元素的最大值，只需要检查新添加的元素即可。 - user2261062

@HatimZahid 不是楼主，但我认为它的时间复杂度是 ~ O(n²)，因为对于每个 for 循环的迭代 i，您需要扫描两个长度为 n 的列表切片，一个是 max（O(i) 时间复杂度），另一个是 min（O(n-i) 时间复杂度）。 - jfaccioni

@jfaccioni 是的，它是O(n²)。您扫描的列表仅用于最大值，其长度为1+2+3+4+...+N，这就是高斯求和公式，相当于(N²+N)/2，其中N²在大N时占主导地位。对于最小值，情况相反，但操作数量相同，因此时间复杂度也相同。 - haxor789

@haxor789 或者你可以说，在每次循环迭代中，整个列表都会被 min 和 max 组合处理。 - Kelly Bundy

@KellyBundy 但那会太明显了（我完全没注意到）。谢谢你指出来。 :) - haxor789

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__)

- Kelly Bundy

---

我不明白这怎么是线性时间。max和min的时间复杂度是O(n)。而且，不确定切片是否是一个好主意，因为它会创建列表的副本。 - Jacques Gaudin

@JacquesGaudin 我的意思是，显然的想法是通过遍历列表并比较相邻元素来创建最大值和最小值的列表。因此，它本质上是3*N，这将是N的复杂度，而不是N²。 - haxor789

@haxor789: 你怎么得到3 * N？左右两边的最大值和最小值分别计算了N步，所以我得到了O(N²)。我有什么遗漏吗？此外，创建的列表数量让我非常怀疑。有人有时间进行基准测试吗？ - Jacques Gaudin

我认为在这种情况下，reversed(acc(t[:0:-1], min)) 等同于 [*acc(t[:0:-1], min)][::-1]。 - Stef

甚至可以使用reversed(acc(reversed(t), min))。我没有对其进行基准测试，但在我看来更易读。 - Stef

Answer 2

我的答案与Kelly的非常相似 - 我们都计算有效拆分点的最小值和最大值，然后检查每个拆分点上的条件。

我比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参数使用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

- Paddy3118

---

不错的测试数据生成器。当我重新进行基准测试时，我可能会使用它。 - Kelly Bundy

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

很简单，只有在可能不同时才计算最大/最小值。

- joostblack

---

如果列表是[1,2,3,4,5]，那么它不会得出正确的答案。 - Student

仍然只有O(n^2)。 - Kelly Bundy

你需要交换第一个和第三个if条件语句来解决这个问题。因为你在检查之前已经改变了最小值。 - haxor789

@KellyBundy 这是O(n²)吗？我的意思是在最坏的情况下，比如完全有序的列表，它将是O(n²)，但在最好的情况下它也可以是O(n)。 - haxor789

@Kodtld，你是对的。现在应该已经修复了。 - joostblack

@KellyBundy，你是对的。但在大多数情况下应该更快。 - joostblack

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

- Student