解题思路
对每个座位号前缀集合 Si，令 Mi=max(Si)，Di=∣Si∣（不同元素个数）。要补成排列 1..m，必须 m≥Mi，此时已有元素都 ≤m，插入数为 m−Di。m 越大插入越多，故最优取 m=Mi，答案为
ansi=Mi−Di.
线性扫描维护当前最大值与去重集合即可。
题目内容
剧院检票系统只找回了一条长度为 n 的座位号残片 a1,a2,…,an，其中每个 ai 都是正整数。对每个前缀 a1,…,ai，把它的元素集合 Si 补成某个排列 {1,2,…,m}：必须有 m 不小于 Si 中的任何元素，且插入尽可能少的缺失整数。系统要据此估计每个前缀至少还缺多少个座位号。
长度为 m 的排列是 1 到 m 各出现一次的序列。请对每个前缀输出最少需要插入的个数。
约束：序列长度不超过 200000，每个 ai 不超过 1000000000。
输入描述
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
