CodeForces竞赛#771问题的时间复杂性

Question

目前，我正试图从CodeForces中解决一个问题，而且我面临着太多的时间问题。我尝试过各种各样的修改，但是我的代码仍然没有被提交。

关于如何提高代码的时间复杂度，有什么建议吗？

这个问题的主要观点可以在这里找到：https://codeforces.com/contest/1638/problem/C

对这一问题的描述如下：

给你一个排列p_1，p_2，…然后，以以下方式构造一个无向图:在顶点i，j之间添加一个边，使我 p_j。您的任务是计算该图中的连通组件数。

两个顶点u和v属于同一连通分量当且仅当沿边至少有一条连接u和v的路径。

置换是由从1到n的n个不同整数以任意顺序组成的数组。例如，2,3,1,5,4是置换，但1,2,2不是置换(2在数组中出现两次)，1,3,4也不是置换(n=3，但数组中有4)。

输入

每个测试包含多个测试用例。第一行包含一个整数t (1≤t≤10**5) --测试用例的数量。下面是测试用例的描述。

每个测试用例的第一行包含一个整数n (1≤n≤10**5) --置换的长度。

每个测试用例的第二行包含n个整数p_1、p_2、…。、p_n (1≤p_i≤n) -排列的元素。

保证所有测试用例上n的和不超过2⋅10**5。

输出

对于每个测试用例，打印一个整数k-连接组件的数量。

import sys
input = sys.stdin.readline
     
for case in range(int(input())):
    length = int(input())
    line = list(map(int, input().split()))
    
    quantity = 0
    for i in range(1, length):
        if line[i] > line[i-1] and max(line[:i]) < min(line[i:]):
            quantity += 1
                
    print(1 if quantity >= length else quantity + 1)

谢谢你的帮忙!

Answer 1

这实现了我的最小/最大缓存方案。我没有提交这个，所以我不知道它是否会符合时间。这是O(3N)而不是O(N*N)，所以对于短列表需要稍长的时间，但是对于长列表应该更好。

您不需要执行input = sys.stdin.readline；实际上，input函数就是这样的。而且，最后一行中的if子句使我感到困惑。最后的for不能超过长度-1次迭代，所以quantity永远不能是>=长度。

import sys
     
for case in range(int(input())):
    length = int(input())
    line = list(map(int, input().split()))
    maxx = 0
    maxs = []
    for i in line:
        if i > maxx:
            maxx = i
        maxs.append(maxx)
    minx = 999999
    mins = []
    for i in line[::-1]:
        if i < minx:
            minx = i
        mins.insert(0,minx)
    
    quantity = 0
    for i in range(1, length):
        if line[i] > line[i-1] and maxs[i-1] < mins[i]:
            quantity += 1
                
    print(quantity + 1)

您可以用理解替换代码的最后一节，尽管我认为这是一种微观优化：

    quantity = sum(
        line[i] > line[i-1] and maxs[i-1] < mins[i]
        for i in range(1, length)
    )
                
    print(quantity + 1)