在Python中找到线性时间中大小为3的排序子序列
假设我们有一个N个数字的数组，我们必须检查3个元素是否在线性（O(n)）时间内b[i]<b[j]<b[k]和i<j<k。如果有多个这样的三胞胎，则打印其中任何一个。
因此，如果输入类似于[13，12，11，6，6，7，3，31]，那么输出将为[6,7,31]
为了解决这个问题，我们将遵循以下步骤-
n：=A的大小
最大值：=n-1，最小值：=0
更小：=大小为1000的数组，并用0填充
较小[0]：=-1
对于1到n范围内的i，执行
更小[i]：=最小值
最低：=我
小[i]：=-1
如果A[i]<=A[最小值]，则
除此以外，
更大：=大小为1000的数组，并用0填充
更大[n-1]：=-1
对于范围在n-2到-1之间的i，将其减小1，
更大[i]：=最大值
最大：=我
更大[i]：=-1
如果A[i]>=A[最大]，则
除此以外，
对于0到n范围内的i，执行
返回A[smaller[i]]，A[i]，A[greater[i]]
如果更小[i]与-1不相同，而更大[i]与-1不相同，则
返回“无”
示例
让我们看下面的实现以更好地理解-
def find_inc_seq(A):
n = len(A)
maximum = n-1
minimum = 0
smaller = [0]*10000
smaller[0] = -1
for i in range(1, n):
if (A[i] <= A[minimum]):
minimum = i
smaller[i] = -1
else:
smaller[i] = minimum
greater = [0]*10000
greater[n-1] = -1
for i in range(n-2, -1, -1):
if (A[i] >= A[maximum]):
maximum = i
greater[i] = -1
else:
greater[i] = maximum
for i in range(0, n):
if smaller[i] != -1 and greater[i] != -1:
return A[smaller[i]], A[i], A[greater[i]]
return "Nothing"
arr = [13, 12, 11, 6, 7, 3, 31]
print(find_inc_seq(arr) )输入值
[13, 12, 11, 6, 7, 3, 31]
输出结果
(6, 7, 31)