蓝桥骑士
一眼看出是最长上升子序列,但是普通的写法是n方的,会超时,所以要用单调队列优化
单调队列优化思想:维护一个单调的队列,新来的元素通过二分找到适当位置,并进行置换
这里维护的是单调递增的队列,队列中的每个元素都严格大于它的前一个元素
当有新元素x时,找到最大的比它严格小的元素q[i]
为了维持队列的单调性,i+1为x的正确放置位置,即:q[i + 1] = x
如果q[i + 1] == x,则令q[i + 1] = x并没有任何问题
如果q[i + 1] > x,分两种情况
如果q[i]是队列的最后一个元素,则q[i + 1] = x相当于新元素入队,使队列长度加一。
如果q[i]不是队列的最后一个元素,也就是说q[i + 1]也是队列中的元素,那么对于之后的元素x’,如果x’ > q[i + 1] 则肯定也有 x’ > x。因此将q[i + 1]换成x不会对队列有影响。
import sys; readline = sys.stdin.readline
read = lambda: [int(x) for x in readline().split()]
n, = read()
arr = read()
q = [0] * (n + 1)
ans = 0
for x in arr:
l = 0; r = ans
# 二分查找最大的小于x的数
while l < r:
mid = l + r + 1 >> 1
if q[mid] < x: l = mid
else: r = mid - 1
q[r + 1] = x
ans = max(ans, r + 1)
# 注意q[0]没有被使用过
print(ans)