题解 | 合唱队

import bisect
def lis(nums):
    tail = []
    res = []
    for x in nums:
        pos = bisect.bisect_left(tail, x)
        if pos == len(tail):
            tail.append(x)
        else:
            tail[pos]=x
        
        res.append(pos+1)
    return res
n = int(input())
nums = list(map(int, input().split()))
left = lis(nums)
right = lis(nums[::-1])[::-1]
max_len = max(l + r - 1 for l, r in zip(left, right))
print(n-max_len)

这题真是难倒我了，坐这一下午，容易想到用二分查找优化双重循环，但是主要是要用一个空集去维护严格递增序列, 重点是想清楚追加/替换后 len = pos + 1 这个点是以输入x为参考的。最后也是参考了其他人的答案里面很妙的反转两次，索引对齐。然后用max_len = max(l+r-1 for l, r in zip(left, right))优化了原本的 max_len=[] for i in range(n): max_len=max(max_len, left[i]+right[i]-1)